Algorithms and Complexity | 6th Italian Conference, CIAC 2006, Rome, Italy, May 29-31, 2006, Proceedings | ISBN 9783540343752

Algorithms and Complexity

6th Italian Conference, CIAC 2006, Rome, Italy, May 29-31, 2006, Proceedings

herausgegeben von Tiziana Calamoneri, Irene Finocchi und Guiseppe F. Italiano
Mitwirkende
Herausgegeben vonTiziana Calamoneri
Herausgegeben vonIrene Finocchi
Herausgegeben vonGuiseppe F. Italiano
Buchcover Algorithms and Complexity  | EAN 9783540343752 | ISBN 3-540-34375-X | ISBN 978-3-540-34375-2

Algorithms and Complexity

6th Italian Conference, CIAC 2006, Rome, Italy, May 29-31, 2006, Proceedings

herausgegeben von Tiziana Calamoneri, Irene Finocchi und Guiseppe F. Italiano
Mitwirkende
Herausgegeben vonTiziana Calamoneri
Herausgegeben vonIrene Finocchi
Herausgegeben vonGuiseppe F. Italiano

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.