Change font size
Change page layout
Change menu position
Sapienza University of Rome    
CIAC 2007

Download the CIAC 2010 program in PDF format PDF icon

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.

XHTML 1.0 | CSS 2.1 | Design by Saverio Caminiti | Inspired by fusion