Home
Call for Papers
Committees
Important Dates
Proceedings
Submission
Registration
Venue
Accommodations
Social Event
VISA
Program
Invited Talks
Accepted Papers
IMPORTANT DATES
Submission: Dec 11, 2009
Acceptance: Feb 13, 2010
Camera Ready: Mar 12, 2010
Conference: May 26‑28, 2010
SPONSORS
7th International Conference on
Algorithms and Complexity
May 26-28, 2010 Rome, Italy
Download the CIAC 2010 program in PDF format 
May 26
9.00—9.30: Opening
9.30—10.30: Invited Talk by Giuseppe F. Italiano
introduced by Rossella Petreschi
10.30—10.50: Coffee Break
Session: Graph Algorithms I chair: Vangelis Th. Paschos
10.50—11.15: Faisal N. Abu-Khzam, Amer E. Mouawad, and Mathieu Liedloff. An Exact Algorithm for Connected Red-Blue Dominating Set.
11.15—11.40: Martin Olsen. Maximizing PageRank with new Backlinks.
11.40—12.05: Bingbing Zhuang and Hiroshi Nagamochi. Enumerating Rooted Graphs with Reflectional Block Structures.
12.05—12.30: Hans-Joachim Böckenhauer, Ralf Klasing, Tobias Mömke, and Monika Steinová. Improved Approximations for TSP with Simple Precedence Constraints.
12.30—12.55: Johan M. M. van Rooij. Polynomial Space Algorithms for Counting Dominating Sets and the Domatic Number.
12.55—14.15: Lunch
Session: Computational complexity chair: Nicola Galesi
14.15—14.40: Leizhen Cai and Boting Yang. Parameterized Complexity of Even/Odd Subgraph Problems.
14.40—15.05: Péter Biró, Rob Irving, and David Manlove. Popular matchings in the Marriage and Roommates problems.
15.05—15.30: Ching-Lueh Chang and Yuh-Dauh Lyuu. Bounding the number of tolerable faults in majority-based systems.
15.30—15.55: Pinar Heggernes, Federico Mancini, Jesper Nederlof, and Yngve Villanger. A parameterized algorithm for Chordal Sandwich.
15.55—16.20: Dana Ron and Gilad Tsur. Testing computability by width-2 OBDDs where the variable order is unknown.
16.20—16.40: Coffee Break
Session: Graph Coloring & Game theory chair: Dieter Mitsche
16.40—17.05: Panagiotis Cheilaris and Géza Tóth. Graph unique-maximum and conflict-free colorings.
17.05—17.30: Bruno Escoffier, Laurent Gourvès, and Jérôme Monnot. Strategic Coloring of a Graph.
17.30—17.55: Rahul Tripathi, Elena Valkanova, and V. S. Anil Kumar. On Strategy Improvement Algorithms for Simple Stochastic Games.
17.55—18.20: Janina Brenner and Guido Schäfer. Online Cooperative Cost Sharing.
May 27
9.30—10.30: Invited Talk by Ricardo Baeza-Yates
introduced by Giorgio Ausiello
10.30—10.50: Coffee Break
Session: Tree Algorithms and Tree Decompositions chair: Peter Widmayer
10.50—11.15: Reinhard Pichler, Stefan Rümmele, and Stefan Woltran. Multicut Algorithms via Tree Decompositions.
11.15—11.40: Hans-Joachim Böckenhauer, Karin Freiermuth, Juraj Hromkovič, Tobias Mömke, Andreas Sprock, and Björn Steffen. The Steiner Tree Reoptimization Problem with Sharpened Triangle Inequality.
11.40—12.05: Bart Jansen. Kernelization for Maximum Leaf Spanning Tree with Positive Vertex Weights.
12.05—12.30: Marek Cygan, Łukasz Kowalik, and Borut Lužar. A Planar Linear Arboricity Conjecture.
12.30—14.00: Lunch
14.00—15.00: Invited Talk by Bruce Reed
introduced by Josep Díaz
Session: Computational Geometry chair: Josep Díaz
15.00—15.25: Dieter Mitsche, Maria Saumell, and Rodrigo I. Silveira. On the Number of Higher Order Delaunay Triangulations.
15.25—15.50: Jérémie Chalopin, Shantanu Das, Yann Disser, Matúš Mihalák, and Peter Widmayer. How simple robots benefit from looking back.
16.00—23.00: Social Event and Social Dinner
May 28
9.30—10.30: Invited Talk by Monika Henzinger
introduced by Tiziana Calamoneri
10.30—10.50: Coffee Break
Session: Graph Algorithms II chair: Maurizio Patrignani
10.50—11.15: Burkhard Monien and Tobias Tscheuschner. On the power of nodes of degree four in the local max-cut problem.
11.15—11.40: Jérémie Chalopin and Daniël Paulusma. Packing Bipartite Graphs with Covers of Complete Bipartite Graphs.
12.05—12.30: Marek Cygan, Marcin Pilipczuk, and Jakub Wojtaszczyk. Irredundant set faster than O(2n).
11.40—12.05: Dorothea Baumeister, Felix Brandt, Felix Fischer, Jan Hoffmann, and Jörg Rothe. The Complexity of Computing Minimal Unidirectional Covering Sets.
12.30—12.55: Daniel Binkele-Raible, Henning Fernau, Alexander Langer, Ljiljana Brankovic, Joachim Kneis, Peter Rossmanith, Mathieu Liedloff, and Dieter Kratsch. A Parameterized Route to Exact Puzzles: Breaking the 2n-Barrier for irredundance.
12.55—14.15: Lunch
14.15—15.15: Invited Talk by Eran Halperin
introduced by Irene Finocchi
Session: String & Network Algorithms chair: Irene Finocchi
15.15—15.40: Torben Hagerup and Gianni Franceschini. Finding the Maximum Suffix with Fewer Comparisons.
15.40—16.05: Daniel Dressler and Martin Strehler. Capacitated Confluent Flows: Complexity and Algorithms.
16.05—16.30: Reinhard Bauer, Tobias Columbus, Bastian Katz, Marcus Krug, and Dorothea Wagner. Preprocessing Speed-Up Techniques is Hard.
16.30—16.55: Jen-Hou Chou and Chi-Jen Lu. Communication Requirements for Stable Marriages.