Final Program
| Monday May 29, 2006 | |
| 8.30-9.15 | Registration |
| 9.15-9.30 | Opening |
| 9.30-10.30 | Invited talk - Kurt Mehlhorn, |
| 10.30-10.55 | Coffee Break |
| Session 1 - Chair: Giuseppe F. Italiano | |
| 10.55-11.20 | "Covering a Set of Points with a Minimum Number of Lines", Magdalene Grantson, Christos Levcopoulos |
| 11.20-11.45 | "Approximation Algorithms for Capacitated Rectangle Stabbing", |
11.45-12.10 |
"In-Place Randomized Slope Selection", |
| Session 2 - Chair: Jan Vahrenhold | |
| 12.10-12.35 | "Quadratic Programs and min weight product problems", Walter Kern, Gerhard Woeginger |
| 12.35-1.00pm | "Counting All Solutions of Minimum Weight Exact Satisfiability", Stefan Porschen |
| 1.00-1.25pm | "Clause Shortening Combined with Pruning Yields a New Upper Bound for Deterministic SAT Algorithms", Evgeny Dantsin, Edward A. Hirsch, Alexander Wolpert |
| 1.25-2.50pm | Lunch break |
| Session 3 - Chair: Guy Even | |
| 2.50-3.15pm | "Network Discovery and Verification with Distance Queries", Thomas Erlebach, Alexander Hall, Michael Hoffmann, Matus Mihalak |
| 3.15-3.40pm | "Deciding the FIFO stability of networks in polynomial time" Maik Weinard |
| 3.40-4.05pm | "Heterogenous Networks can be Unstable at Arbitrarily Low Injection Rates", Dimitrios Koukopoulos, Stavros D. Nikolopoulos |
| 4.05-4.30pm | Coffee Break |
| Session 4 - Chair: Irene Finocchi | |
| 4.30-4.55pm | "Provisioning a Virtual Private Network Under the Presence of Non-Communicating Groups" Friedrich Eisenbrand, Edda Happ |
| 4.55-5.20pm | "On the Hardness of Range Assignment Problems", Bernhard Fuchs |
| 5.20-5.45pm | "Gathering Algorithms on Paths under Interference Constraints", Jean-Claude Bermond, Ricardo Correa, Joseph Yu |
| Tuesday May 30, 2006 | |
| 9.00-10.00 | Invited talk - Franco P. Preparata, |
| Session 5 - Chair: Giorgio Ausiello | |
| 10.00-10.25 | "Black Hole Search in Asynchronous Rings Using Tokens", S. Dobrev, R. Kralovic, N. Santoro, Wei Shi |
| 10.25-10.50 | "On Broadcast Scheduling With Limited Energy", |
10.50-11.15 |
"A Near Optimal Scheduler for On-demand Data Broadcasts", |
| 11.15-11.40 | Coffee Break |
| Session 6 - Chair: Tiziana Calamoneri | |
| 11.40-12.05 | "Fair Cost-Sharing Methods for Scheduling Jobs on Parallel Machines", Yvonne Bleischwitz, Burkhard Monien |
| 12.05-12.30 | "Tighter Approximation Bounds for LPT Scheduling in Two Special Cases", Annamaria Kovacs |
| 12.30-12.55 | "Inapproximability results for orthogonal rectangle packing problems with rotations", Miroslav Chlebik, Janka Chlebikova |
| 1.00-2.20pm | Lunch break |
| Session 7 - Chair: Uli Meyer | |
| 2.20-2.45pm | "Approximate Hierarchical Facility Location and
Applications to the Shallow Steiner Tree and Range Assignment Problems" Erez Kantor, David Peleg |
| 2.45-3.10pm | "An Approximation Algorithm for a Bottleneck Traveling
Salesman Problem" Ming-Yang Kao, Manan Sanghi |
| 3.10-3.35pm | "On the Minimum Common Integer Partition Problem",, Xin Chen, Lan Liu, Zheng Liu, Tao Jiang |
| 4.30pm | Social Event |
| Wednesday May 31, 2006 | |
| 9.00-10.00 | Invited talk - Pavel Pudlak, |
| Session 8 - Chair: Rossella Petreschi | |
| 10.00-10.25 | "Matching Subsequences in Trees", Philip Bille, Inge Li Goertz |
| 10.25-10.50 | "Distance Approximating Trees: Complexity and Algorithms", |
10.50-11.15 |
"How to Pack Directed Acyclic Graphs into Small Blocks", |
| 11.15-11.40 | Coffee Break |
| Session 9 - Chair: Anna Ostlin Pagh | |
| 11.40-12.05 | "On-line coloring of H-free bipartite graphs" Hajo Broersma, Agostino Capponi, Daniel Paulusma |
| 12.05-12.30 | "Distributed approximation algorithms for planar graphs", Andrzej Czygrinow, Michal Hanckowiak, Edyta Szymanska |
| 12.30-12.55 | "A New NC-algorithm for Finding a Perfect Matching in d-regular Bipartite Graphs when d is Small", Raghav Kulkarni |
| 1.00-2.20pm | Lunch break |
| Session 10 - Chair: Nicola Galesi | |
| 2.20-2.45pm | "Fixed-Parameter Tractability Results for Feedback Set Problems in Tournaments", Michael Dom, Jiong Guo, Falk Hueffner, Rolf Niedermeier, Anke Truss |
| 2.45-3.10pm | "Parameterized Algorithms for Hitting Set: the Weighted Case", Henning Fernau |
| 3.10-3.35pm | "Fixed-Parameter Tractable Generalizations of Cluster Editing", Peter Damaschke |
| 3.35-4.00pm | Coffee Break |
| Session 11 - Chair: Peter Damaschke | |
| 4.00-4.25pm | "The Linear Arrangement Problem Parameterized Above Guaranteed Value", Gregory Gutin, Arash Rafiey, Stefan Szeider, Anders Yeo |
| 4.25-4.50pm | "Universal relations and #P-completeness", Hervé Fournier, Guillaume Malod |
| 4.50-5.15pm | "Locally 2-dimensional Sperner Problems Complete for the Polynomial Parity Argument Classes" Katalin Friedl, Gabor Ivanyos, Miklos Santha, Yves F. Verhoeven |
Fax: +39-06-8541842
E-mail:ciac@di.uniroma1.it