6th Conference on Algorithms and Complexity
May 29-31, 2006 Rome, Italy

Final Program

Monday May 29, 2006
8.30-9.15 Registration
9.15-9.30 Opening

Invited talk - Kurt Mehlhorn,
"Reliable and Efficient Geometric Computing"

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

"Approximation Algorithms for Capacitated Rectangle Stabbing",
Guy Even, Dror Rawitz, Shimon (Moni) Shahar


"In-Place Randomized Slope Selection",
Henrik Blunck and Jan Vahrenhold

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

Invited talk - Franco P. Preparata,
"Beware of the model: reflections on algorithmic research"

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

"On Broadcast Scheduling With Limited Energy",
Christian Gunia


"A Near Optimal Scheduler for On-demand Data Broadcasts",
Hing-fung Ting

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

Invited talk - Pavel Pudlak,
"On search problems in complexity theory and in logic"

Session 8 - Chair: Rossella Petreschi
10.00-10.25 "Matching Subsequences in Trees",
Philip Bille, Inge Li Goertz

"Distance Approximating Trees: Complexity and Algorithms",
Feodor F. Dragan, Chenyu Yan


"How to Pack Directed Acyclic Graphs into Small Blocks",
Yuichi Asahiro, Tetsuya Furukawa, Keiichi Ikegami, Eiji Miyano

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

Computer Science Department home page