Algorithms and Complexity

1. Front Matter

   Pages I-XV

   PDF

2. Communication, Dynamics, and Renormalization

   • Bernard Chazelle

   Pages 1-32

3. “Green” Barrier Coverage with Mobile Sensors

   • Amotz Bar-Noy, Dror Rawitz, Peter Terlecky

   Pages 33-46

4. A Refined Complexity Analysis of Finding the Most Vital Edges for Undirected Shortest Paths

   • Cristina Bazgan, André Nichterlein, Rolf Niedermeier

   Pages 47-60

5. Orthogonal Graph Drawing with Inflexible Edges

   • Thomas Bläsius, Sebastian Lehmann, Ignaz Rutter

   Pages 61-73

6. Linear Time Constructions of Some \(d\)-Restriction Problems

   • Nader H. Bshouty

   Pages 74-88

7. Efficiently Testing \(T\)-Interval Connectivity in Dynamic Graphs

   • Arnaud Casteigts, Ralf Klasing, Yessin M. Neggaz, Joseph G. Peters

   Pages 89-100

8. Competitive Strategies for Online Clique Clustering

   • Marek Chrobak, Christoph Dürr, Bengt J. Nilsson

   Pages 101-113

9. Scheduling with Gaps: New Models and Algorithms

   • Marek Chrobak, Mordecai Golin, Tak-Wah Lam, Dorian Nogneng

   Pages 114-126

10. MinMax-Distance Gathering on Given Meeting Points

    • Serafino Cicerone, Gabriele Di Stefano, Alfredo Navarra

    Pages 127-139

11. Evacuating Robots from a Disk Using Face-to-Face Communication (Extended Abstract)

    • J. Czyzowicz, K. Georgiou, E. Kranakis, L. Narayanan, J. Opatrny, B. Vogtenhuber

    Pages 140-152

12. Planarity of Streamed Graphs

    • Giordano Da Lozzo, Ignaz Rutter

    Pages 153-166

13. Clique-Width of Graph Classes Defined by Two Forbidden Induced Subgraphs

    • Konrad K. Dabrowski, Daniël Paulusma

    Pages 167-181

14. Randomized Adaptive Test Cover

    • Peter Damaschke

    Pages 182-193

15. Contraction Blockers for Graphs with Forbidden Induced Paths

    • Öznur Yaşar Diner, Daniël Paulusma, Christophe Picouleau, Bernard Ries

    Pages 194-207

16. On the Complexity of Wafer-to-Wafer Integration

    • Guillerme Duvillié, Marin Bougeret, Vincent Boudet, Trivikram Dokka, Rodolphe Giroudeau

    Pages 208-220

17. Label Placement in Road Maps

    • Andreas Gemsa, Benjamin Niedermann, Martin Nöllenburg

    Pages 221-234

18. Discrete Stochastic Submodular Maximization: Adaptive vs. Non-adaptive vs. Offline

    • Lisa Hellerstein, Devorah Kletenik, Patrick Lin

    Pages 235-248

19. Parameterized Algorithms and Kernels for 3-Hitting Set with Parity Constraints

    • Vikram Kamat, Neeldhara Misra

    Pages 249-260

20. Simple Strategies Versus Optimal Schedules in Multi-agent Patrolling

    • Akitoshi Kawamura, Makoto Soejima

    Pages 261-273

This book constitutes the refereed conference proceedings of the 9th International Conference on Algorithms and Complexity, CIAC 2015, held in Paris, France, in May 2015.

The 30 revised full papers presented were carefully reviewed and selected from 93 submissions and are presented together with 2 invited papers. The papers present original research in the theory and applications of algorithms and computational complexity.

• Algorithmic game theory
• Approximation algorithms
• Combinatorial optimization
• Combinatorics
• Computational complexity
• Data structures design and analysis
• Design and analysis of algorithms
• Discrete mathematics
• Geometry and discrete structures
• Graph theory
• Mechanism design
• Online algorithms
• Parameterized complexity and exact algorithms
• Probabilistic algorithms
• Probabilistic computation
• Randomness
• Streaming models
• Sublinear and near linear time algorithms
• algorithm analysis and problem complexity
• data structures

• LAMSADE, Université Paris-Dauphine, Paris Cedex 16, France

  Vangelis Th. Paschos

• Inst. of Theoretical Computer Science, ETH Zürich, Zürich, Switzerland

  Peter Widmayer

Policies and ethics