6. CIAC 2006: Rome, Italy

Invited Talks

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

Session 1

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

Session 2

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

Session 3

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

Session 4

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

Session 5

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

Session 6

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

Session 7

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

Session 8

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

Session 9

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

Session 10

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

Session 11

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