Algorithms and Complexity

Inhaltsverzeichnis

• Invited Talks.
• Reliable and Efficient Geometric Computing.
• Beware of the Model: Reflections on Algorithmic Research.
• On Search Problems in Complexity Theory and in Logic (Abstract).
• Session 1.
• Covering a Set of Points with a Minimum Number of Lines.
• Approximation Algorithms for Capacitated Rectangle Stabbing.
• In-Place Randomized Slope Selection.
• Session 2.
• Quadratic Programming and Combinatorial Minimum Weight Product Problems.
• Counting All Solutions of Minimum Weight Exact Satisfiability.
• Clause Shortening Combined with Pruning Yields a New Upper Bound for Deterministic SAT Algorithms.
• Session 3.
• Network Discovery and Verification with Distance Queries.
• Deciding the FIFO Stability of Networks in Polynomial Time.
• Heterogenous Networks Can Be Unstable at Arbitrarily Low Injection Rates.
• Session 4.
• Provisioning a Virtual Private Network Under the Presence of Non-communicating Groups.
• Gathering Algorithms on Paths Under Interference Constraints.
• On the Hardness of Range Assignment Problems.
• Session 5.
• Black Hole Search in Asynchronous Rings Using Tokens.
• On Broadcast Scheduling with Limited Energy.
• A Near Optimal Scheduler for On-Demand Data Broadcasts.
• Session 6.
• Fair Cost-Sharing Methods for Scheduling Jobs on Parallel Machines.
• Tighter Approximation Bounds for LPT Scheduling in Two Special Cases.
• Inapproximability Results for Orthogonal Rectangle Packing Problems with Rotations.
• Session 7.
• Approximate Hierarchical Facility Location and Applications to the Shallow Steiner Tree and Range Assignment Problems.
• An Approximation Algorithm for a Bottleneck Traveling Salesman Problem.
• On the Minimum Common Integer Partition Problem.
• Session 8.
• Matching Subsequences in Trees.
• Distance Approximating Trees: Complexity and Algorithms.
• How to PackDirected Acyclic Graphs into Small Blocks.
• Session 9.
• On-Line Coloring of H-Free Bipartite Graphs.
• Distributed Approximation Algorithms for Planar Graphs.
• A New NC-Algorithm for Finding a Perfect Matching in d-Regular Bipartite Graphs When d Is Small.
• Session 10.
• Fixed-Parameter Tractability Results for Feedback Set Problems in Tournaments.
• Parameterized Algorithms for Hitting Set: The Weighted Case.
• Fixed-Parameter Tractable Generalizations of Cluster Editing.
• Session 11.
• The Linear Arrangement Problem Parameterized Above Guaranteed Value.
• Universal Relations and #P-Completeness.
• Locally 2-Dimensional Sperner Problems Complete for the Polynomial Parity Argument Classes.