6. CIAC 2006: Rome, Italy

Tiziana Calamoneri, Irene Finocchi, Giuseppe F. Italiano (Eds.): Algorithms and Complexity, 6th Italian Conference, CIAC 2006, Rome, Italy, May 29-31, 2006, Proceedings. Lecture Notes in Computer Science 3998 Springer 2006, ISBN 3-540-34375-X BibTeX

Invited Talks

Kurt Mehlhorn:
Reliable and Efficient Geometric Computing. 1-2
Electronic Edition (link) BibTeX
Franco P. Preparata:
Beware of the Model: Reflections on Algorithmic Research. 3-4
Electronic Edition (link) BibTeX
Pavel Pudlák:
On Search Problems in Complexity Theory and in Logic (Abstract). 5
Electronic Edition (link) BibTeX

Magdalene Grantson, Christos Levcopoulos:
Covering a Set of Points with a Minimum Number of Lines. 6-17
Electronic Edition (link) BibTeX
Guy Even, Dror Rawitz, Shimon Shahar:
Approximation Algorithms for Capacitated Rectangle Stabbing. 18-29
Electronic Edition (link) BibTeX
Henrik Blunck, Jan Vahrenhold:
In-Place Randomized Slope Selection. 30-41
Electronic Edition (link) BibTeX

Walter Kern, Gerhard J. Woeginger:
Quadratic Programming and Combinatorial Minimum Weight Product Problems. 42-49
Electronic Edition (link) BibTeX
Stefan Porschen:
Counting All Solutions of Minimum Weight Exact Satisfiability. 50-59
Electronic Edition (link) BibTeX
Evgeny Dantsin, Edward A. Hirsch, Alexander Wolpert:
Clause Shortening Combined with Pruning Yields a New Upper Bound for Deterministic SAT Algorithms. 60-68
Electronic Edition (link) BibTeX

Thomas Erlebach, Alexander Hall, Michael Hoffmann, Matús Mihalák:
Network Discovery and Verification with Distance Queries. 69-80
Electronic Edition (link) BibTeX
Maik Weinard:
Deciding the FIFO Stability of Networks in Polynomial Time. 81-92
Electronic Edition (link) BibTeX
Dimitrios Koukopoulos, Stavros D. Nikolopoulos:
Heterogenous Networks Can Be Unstable at Arbitrarily Low Injection Rates. 93-104
Electronic Edition (link) BibTeX

Friedrich Eisenbrand, Edda Happ:
Provisioning a Virtual Private Network Under the Presence of Non-communicating Groups. 105-114
Electronic Edition (link) BibTeX
Jean-Claude Bermond, Ricardo C. Corrêa, Min-Li Yu:
Gathering Algorithms on Paths Under Interference Constraints. 115-126
Electronic Edition (link) BibTeX
Bernhard Fuchs:
On the Hardness of Range Assignment Problems. 127-138
Electronic Edition (link) BibTeX

Stefan Dobrev, Rastislav Kralovic, Nicola Santoro, Wei Shi:
Black Hole Search in Asynchronous Rings Using Tokens. 139-150
Electronic Edition (link) BibTeX
Christian Gunia:
On Broadcast Scheduling with Limited Energy. 151-162
Electronic Edition (link) BibTeX
Hing-Fung Ting:
A Near Optimal Scheduler for On-Demand Data Broadcasts. 163-174
Electronic Edition (link) BibTeX

Yvonne Bleischwitz, Burkhard Monien:
Fair Cost-Sharing Methods for Scheduling Jobs on Parallel Machines. 175-186
Electronic Edition (link) BibTeX
Annamária Kovács:
Tighter Approximation Bounds for LPT Scheduling in Two Special Cases. 187-198
Electronic Edition (link) BibTeX
Miroslav Chlebík, Janka Chlebíková:
Inapproximability Results for Orthogonal Rectangle Packing Problems with Rotations. 199-210
Electronic Edition (link) BibTeX

Erez Kantor, David Peleg:
Approximate Hierarchical Facility Location and Applications to the Shallow Steiner Tree and Range Assignment Problems. 211-222
Electronic Edition (link) BibTeX
Ming-Yang Kao, Manan Sanghi:
An Approximation Algorithm for a Bottleneck Traveling Salesman Problem. 223-235
Electronic Edition (link) BibTeX
Xin Chen, Lan Liu, Zheng Liu, Tao Jiang:
On the Minimum Common Integer Partition Problem. 236-247
Electronic Edition (link) BibTeX

Philip Bille, Inge Li Gørtz:
Matching Subsequences in Trees. 248-259
Electronic Edition (link) BibTeX
Feodor F. Dragan, Chenyu Yan:
Distance Approximating Trees: Complexity and Algorithms. 260-271
Electronic Edition (link) BibTeX
Yuichi Asahiro, Tetsuya Furukawa, Keiichi Ikegami, Eiji Miyano:
How to Pack Directed Acyclic Graphs into Small Blocks. 272-283
Electronic Edition (link) BibTeX

Hajo Broersma, Agostino Capponi, Daniël Paulusma:
On-Line Coloring of H-Free Bipartite Graphs. 284-295
Electronic Edition (link) BibTeX
Andrzej Czygrinow, Michal Hanckowiak, Edyta Szymanska:
Distributed Approximation Algorithms for Planar Graphs. 296-307
Electronic Edition (link) BibTeX
Raghav Kulkarni:
A New NC-Algorithm for Finding a Perfect Matching in d-Regular Bipartite Graphs When d Is Small. 308-319
Electronic Edition (link) BibTeX

Michael Dom, Jiong Guo, Falk Hüffner, Rolf Niedermeier, Anke Truß:
Fixed-Parameter Tractability Results for Feedback Set Problems in Tournaments. 320-331
Electronic Edition (link) BibTeX
Henning Fernau:
Parameterized Algorithms for Hitting Set: The Weighted Case. 332-343
Electronic Edition (link) BibTeX
Peter Damaschke:
Fixed-Parameter Tractable Generalizations of Cluster Editing. 344-355
Electronic Edition (link) BibTeX

Gregory Gutin, Arash Rafiey, Stefan Szeider, Anders Yeo:
The Linear Arrangement Problem Parameterized Above Guaranteed Value. 356-367
Electronic Edition (link) BibTeX
Hervé Fournier, Guillaume Malod:
Universal Relations and #P-Completeness. 368-379
Electronic Edition (link) BibTeX
Katalin Friedl, Gábor Ivanyos, Miklos Santha, Yves F. Verhoeven:
Locally 2-Dimensional Sperner Problems Complete for the Polynomial Parity Argument Classes. 380-391
Electronic Edition (link) BibTeX