Algorithms and Complexity: 6th Italian Conference, CIAC 2006, Rome, Italy, May 29-31, 2006. Proceedings

Kurt Mehlhorn (auth.), Tiziana Calamoneri, Irene Finocchi, Giuseppe F. Italiano (eds.)354034375X, 9783540343752

This book constitutes the refereed proceedings of the 6th Italian Conference on Algorithms and Computation, CIAC 2006, held in Rome, Italy, in May 2006.

The 33 revised full papers presented together with 3 invited papers were carefully reviewed and selected from 80 submissions. Among the topics addressed are sequential, parallel and distributed algorithms, data structures, approximation algorithms, randomized algorithms, on-line algorithms, graph algorithms, analysis of algorithms, algorithm engineering, algorithmic game theory, computational biology, computational complexity, communication networks, computational geometry, cryptography, discrete optimization, graph drawing, mathematical programming, and quantum algorithms.

---

Table of contents :
Front Matter….Pages –
Reliable and Efficient Geometric Computing….Pages 1-2
Beware of the Model: Reflections on Algorithmic Research….Pages 3-4
On Search Problems in Complexity Theory and in Logic (Abstract)….Pages 5-5
Covering a Set of Points with a Minimum Number of Lines….Pages 6-17
Approximation Algorithms for Capacitated Rectangle Stabbing….Pages 18-29
In-Place Randomized Slope Selection….Pages 30-41
Quadratic Programming and Combinatorial Minimum Weight Product Problems….Pages 42-49
Counting All Solutions of Minimum Weight Exact Satisfiability….Pages 50-59
Clause Shortening Combined with Pruning Yields a New Upper Bound for Deterministic SAT Algorithms….Pages 60-68
Network Discovery and Verification with Distance Queries….Pages 69-80
Deciding the FIFO Stability of Networks in Polynomial Time….Pages 81-92
Heterogenous Networks Can Be Unstable at Arbitrarily Low Injection Rates….Pages 93-104
Provisioning a Virtual Private Network Under the Presence of Non-communicating Groups….Pages 105-114
Gathering Algorithms on Paths Under Interference Constraints….Pages 115-126
On the Hardness of Range Assignment Problems….Pages 127-138
Black Hole Search in Asynchronous Rings Using Tokens….Pages 139-150
On Broadcast Scheduling with Limited Energy….Pages 151-162
A Near Optimal Scheduler for On-Demand Data Broadcasts….Pages 163-174
Fair Cost-Sharing Methods for Scheduling Jobs on Parallel Machines….Pages 175-186
Tighter Approximation Bounds for LPT Scheduling in Two Special Cases….Pages 187-198
Inapproximability Results for Orthogonal Rectangle Packing Problems with Rotations….Pages 199-210
Approximate Hierarchical Facility Location and Applications to the Shallow Steiner Tree and Range Assignment Problems….Pages 211-222
An Approximation Algorithm for a Bottleneck Traveling Salesman Problem….Pages 223-235
On the Minimum Common Integer Partition Problem….Pages 236-247
Matching Subsequences in Trees….Pages 248-259
Distance Approximating Trees: Complexity and Algorithms….Pages 260-271
How to Pack Directed Acyclic Graphs into Small Blocks….Pages 272-283
On-Line Coloring of H-Free Bipartite Graphs….Pages 284-295
Distributed Approximation Algorithms for Planar Graphs….Pages 296-307
A New NC-Algorithm for Finding a Perfect Matching in d -Regular Bipartite Graphs When d Is Small….Pages 308-319
Fixed-Parameter Tractability Results for Feedback Set Problems in Tournaments….Pages 320-331
Parameterized Algorithms for Hitting Set : The Weighted Case….Pages 332-343
Fixed-Parameter Tractable Generalizations of Cluster Editing….Pages 344-355
The Linear Arrangement Problem Parameterized Above Guaranteed Value….Pages 356-367
Universal Relations and #P-Completeness….Pages 368-379
Locally 2-Dimensional Sperner Problems Complete for the Polynomial Parity Argument Classes….Pages 380-391
Back Matter….Pages –