List of accepted papers for SWAT 2006:


The Weighted Maximum-Mean Subtree and Other Bicriterion Subtree Problems
Josiah Carlson and David Eppstein

Exponential time algorithms for the minimum dominating set problem on some graph classes
Serge Gaspers and Dieter Kratsch and Mathieu Liedloff

Sorting by Merging or Merging by Sorting?
Gianni Franceschini

Paging with Request Sets
Leah Epstein and Rob van Stee and Tami Tamir

Decentralization and Mechanism Design for Online Machine Scheduling
Birgit Heydenreich and Rudolf Müller and Marc Uetz

Linear-Time Algorithms for Tree Root Problems
Maw-Shang Chang and Ming-Tat Ko and Hsueh-I Lu

In-Place Algorithms for Computing (Layers of) Maxima
Henrik Blunck and Jan Vahrenhold

On the Approximation Hardness of Some Generalizations of TSP
Hans-Joachim Bockenhauer and Juraj Hromkovic and Joachim Kneis and Joachim Kupke

Improved Algorithms for Quantum Identification of Boolean Oracles
Andris Ambainis and Kazuo Iwama and Akinori Kawachi and Rudy Raymond and Shigeru Yamashita

Scheduling Jobs on Grid Processors
Joan Boyar and Lene M. Favrholdt

Approximability of Minimum AND-Circuits
Jan Arpe and Bodo Manthey

Variable sized online interval coloring with bandwidth
Leah Epstein and Thomas Erlebach and Asaf Levin

Exact computation of maximum induced forest
Igor Razgon

Simultaneous Embedding with Two Bends per Edge in Polynomial Space
Frank Kammer

Online, Non-preemptive Scheduling of Equal-Length Jobs on Two Identical Machines
Michael H. Goldwasser and Mark Pedigo

On spanners of geometric graphs
Joachim Gudmundsson and Michiel Smid

Generalized Powers of Graphs and Their Algorithmic Use
Andreas Brandstaedt and Feodor F. Dragan and Yang Xiang and Chenyu Yan

Approximation of Octilinear Steiner Trees Constrained by Hard and Soft Obstacles
Matthias Mueller-Hannemann and Anna Schulze

On Guarding Rectilinear Domains
Matthew J. Katz and Gabriel S. Roisman

Acyclic Orientation of Drawings
Eyal Ackerman and Kevin Buchin and Christian Knauer and Günter Rote

Largest and Smallest Tours and Convex Hulls for Imprecise Points
Maarten Löffler and Marc van Kreveld

Approximation Algorithms for the Minimum Convex Partition Problem
Christian Knauer and Andreas Spillner

Finding the position of the $k$-mismatch and approximate tandem repeats
Haim Kaplan and Ely Porat and Nira Shafrir

A Simpler Linear-Time Recognition of Circular-Arc Graphs
Haim Kaplan and Yahav Nussbaum

An approximation algorithm for the Wireless Gathering Problem
Vincenzo Bonifaci and Peter Korteweg and Alberto Marchetti-Spaccamela and Leen Stougie

Better Approximation Schemes for Disk Graphs
Erik Jan van Leeuwen

Multiplexing Packets with Arbitrary Deadlines in Bounded Buffers
Y. Azar and N. Levy

Fast subexponential algorithm for non-local problems on graphs of bounded genus
Frederic Dorn and Fedor V. Fomin and Dimitrios M. Thilikos

An tilde O(n^{2.75}) algorithm for online topological ordering
Deepak Ajwani and Tobias Friedrich and Ulrich Meyer

The Node-weighted Steiner Problem in Graphs of Restricted Node Weights
Spyros Angelopoulos

Triangles, 4-cycles and Parameterized (In-) Tractability
Venkatesh Raman and Saket Saurabh

Reoptimization of minimum and maximum traveling salesman's tours
Giorgio Ausiello and Bruno Escoffier and Jerome Monnot and Vangelis Paschos

Unbiased Matrix Rounding
Benjamin Doerr and Tobias Friedrich and Christian Klein and Ralf Osbild

Minimum Membership Set Covering and the Consecutive Ones Property
Michael Dom and Jiong Guo and Rolf Niedermeier and Sebastian Wernicke

Dynamic Matching Markets and Voting Paths
David J. Abraham and Kavitha Telikepalli

Approximating Rational Objectives is as Easy as Approximating Linear Ones
Jose R. Correa and Cristina G. Fernandes and Yoshiko Wakabayashi