Logic List Mailing Archive

SWAT 2006: 10th Scandinavian Workshop on Algorithm Theory, July, Riga (Latvia)

Registration for the 10th Scandinavian Workshop on Algorithm Theory (SWAT
2006, July 6-8 in Riga, Latvia) is now open (at http://www.lumii.lv/swat).
Please note that the early registration deadline is already on April 30.


Priliminary program for the conference
=========================
=============

Wednesday July 5
----------------

18:00-19:00 Registration & Welcome reception


Thursday July 6
---------------

8:30-9:30 Session 1
   Multiplexing Packets with Arbitrary Deadlines in Bounded Buffers
   Y. Azar and N. Levy

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

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

9:30-10:00 Coffee break

10:00-11:00 Session 2
   A Simpler Linear-Time Recognition of Circular-Arc Graphs
   Haim Kaplan and Yahav Nussbaum

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

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

11:00-11:15 Break

11:15-12:15 Invited talk
   Top-Down Analysis of Path Compression: Deriving the
   Inverse-Ackermann Bound Naturally (and Easily)
   Raimund Seidel

12:15-13:30 Lunch

13:30-14:30 Session 3
   Sorting by Merging or Merging by Sorting?
   Gianni Franceschini

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

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

14:30-15:00 Coffee break

15:00-16:00 Session 4
   Online, Non-preemptive Scheduling of Equal-Length Jobs on Two
   Identical Machines
   Michael H. Goldwasser and Mark Pedigo

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

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

16:00-16:15 Break

16:15-17.15 Session 5
   Exponential time algorithms for the minimum dominating set problem
   on some graph classes
   Serge Gaspers, Dieter Kratsch and Mathieu Liedloff

   Exact computation of maximum induced forest
   Igor Razgon

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

Business meeting


Friday July 7
-------------

8:30-9:30 Session 6
   On the Approximation Hardness of Some Generalizations of TSP
   Hans-Joachim Bockenhauer, Juraj Hromkovic, Joachim Kneis and
   Joachim Kupke

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

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

9:30-10:00 Coffee break

10:00-11:00 Session 7
   On Guarding Rectilinear Domains
   Matthew J. Katz and Gabriel S. Roisman

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

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

11:00-11:15 Break

11:15-12:15 Invited talk
   TBD
   Robert E. Tarjan

12:15-13:30 Lunch

13:30-14:30 Session 8
   Simultaneous Embedding with Two Bends per Edge in Polynomial Area
   Frank Kammer

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

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

Excursion to Rundale Palace

Conference dinner


Saturday July 8
---------------

8:30-9:30 Session 9
   Approximability of Minimum AND-Circuits
   Jan Arpe and Bodo Manthey

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

   Better Approximation Schemes for Disk Graphs
   Erik Jan van Leeuwen

9:30-10:00 Coffee break

10:00-11:00 Session 10
   An approximation algorithm for the Wireless Gathering Problem
   Vincenzo Bonifaci, Peter Korteweg, Alberto Marchetti-Spaccamela and
   Leen Stougie

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

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

11:00-11:15 Break

11:15-12:15 Invited talk
   Classic and Quantum Network Coding
   Kazuo Iwama

12:15-13:30 Lunch

13:30-14:30 Session 11
   In-Place Algorithms for Computing (Layers of) Maxima
   Henrik Blunck and Jan Vahrenhold

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

   On spanners of geometric graphs
   Joachim Gudmundsson and Michiel Smid

14:30-15:00 Coffee break

15:00-16:00 Session 12
   The Weighted Maximum-Mean Subtree and Other Bicriterion
   Subtree Problems
   Josiah Carlson and David Eppstein

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

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