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

Accepted Papers

This page contains the list of accepted papers, in no particular order:

Network Discovery and Verification with Distance Queries
Thomas Erlebach, Alexander Hall, Michael Hoffmann, Matus Mihalak

An Approximation Algorithm for a Bottleneck Traveling Salesman Problem
Manan Sanghi

Fair Cost-Sharing Methods for Scheduling Jobs on Parallel Machines
Yvonne Bleischwitz and Burkhard Monien

Inapproximability results for orthogonal rectagle packing problems with rotations
Miroslav Chlebik and Janka Chlebikova

Quadratic Programs and min weight product problems
Walter Kern and Gerhard Woeginger

Covering a Set of Points with a Minimum Number of Lines
Magdalene Grantson, Christos Levcopoulos

Fixed-Parameter Tractability Results for Feedback Set Problems in Tournaments
Michael Dom and Jiong Guo and Falk Hueffner and Rolf Niedermeier and Anke Truss

Matching Subsequences in Trees
Inge Li G¯rtz and Philip Bille

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

Tighter approximation bounds for LPT scheduling in two special cases
Annamaria Kovacs

How to pack directed acyclic graphs into small blocks
Yuichi Asahiro and Tetsuya Furukawa and Keiichi Ikegami and Eiji Miyano

Approximate Hierarchical Facility Location and Applications to the Shallow Steiner Tree and Range Assignment Problems
David Peleg and Erez Kantor

Deciding the FIFO stability of networks in polynomial time
Maik Weinard

On the Hardness of Range Assignment Problems
Bernhard Fuchs

on-line coloring of H-free bipartite graphs
hajo broersma and agostino capponi and daniel paulusma

Universal relations and #P-completeness
Hervè FOURNIER and Guillaume MALOD

Distributed approximation algorithms for planar graphs
Edyta Szymanska and Andrzej Czygrinow and Michal Hanckowiak

A near optimal scheduler for on-demand data broadcasts
Hing-fung Ting

Locally 2-dimensional Sperner problems complete for the polynomial parity argument classes
Katalin Friedl and Gabor Ivanyos and Miklos Santha and Yves F. Verhoeven

Parameterized Algorithms for Hitting Set: the Weighted Case
Henning Fernau

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

A new NC-aglorithm for finding a perfect matching in d-regular bipartite graphs when d is small
Raghav Kulkarni

Provisioning a Virtual Private Network Under the Presence of Non-Communicating Groups
Friedrich Eisenbrand and Edda Happ

The Linear Arrangement Problem Parameterized Above Guaranteed Value
Gregory Gutin and Arash Rafiey and Stefan Szeider and Anders Yeo

Heterogenous Networks can be Unstable at Arbitrarily Low Injection Rates
Dimitrios Koukopoulos and Stavros D. Nikolopoulos

Fixed-Parameter Tractable Generalizations of Cluster Editing
Peter Damaschke

In-Place Randomized Slope Selection
Henrik Blunck and Jan Vahrenhold

On the Minimum Common Integer Partition Problem
Xin Chen and Lan Liu and Zheng Liu and Tao Jiang

Counting All Solutions of Minimum Weight Exact Satisfiability
Stefan Porschen

Black Hole Search in Asynchronous Rings Using Tokens
S. Dobrev and R. Kralovic and N. Santoro and W. Shi

On Broadcast Scheduling With Limited Energy
Christian Gunia

Clause Shortening Combined with Pruning Yields a New Upper Bound for Deterministic SAT Algorithms
Evgeny Dantsin and Edward A. Hirsch and Alexander Wolpert

Gathering Algorithms on Paths under Interference Constraints
Jean-Claude Bermond and Ricardo CorrÍa and Joseph Yu

Fax: +39-06-8541842
E-mail: ciac@di.uniroma1.it

Computer Science Department home page