Calamoneri / Finocchi / Italiano Algorithms and Complexity

6th Italian Conference, CIAC 2006, Rome, Italy, May 29-31, 2006, Proceedings
2006
ISBN: 978-3-540-34378-3
Verlag: Springer
Format: PDF
Kopierschutz: 1 - PDF Watermark

E-Book, Englisch, Band 3998, 396 Seiten, eBook

Reihe: Lecture Notes in Computer Science

Zielgruppe

Research

Autoren/Hrsg.

Calamoneri, Tiziana

Finocchi, Irene

Italiano, Guiseppe F.

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.