
×
Algorithms and Complexity
6th Italian Conference, CIAC 2006, Rome, Italy, May 29-31, 2006, Proceedings
herausgegeben von Tiziana Calamoneri, Irene Finocchi und Guiseppe F. ItalianoInhaltsverzeichnis
- 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.