10. SWAT 2006: Riga, Latvia

Invited Papers

• Raimund Seidel:
  Top-Down Analysis of Path Compression: Deriving the Inverse-Ackermann Bound Naturally (and Easily). 1
  
• Robert Endre Tarjan:
  Results and Problems on Self-adjusting Search Trees and Related Data Structures. 2
  
• Kazuo Iwama:
  Classic and Quantum Network Coding. 3-4
  

Contributed Papers

• Yossi Azar, Nir Levy:
  Multiplexing Packets with Arbitrary Deadlines in Bounded Buffers. 5-16
  
• Joan Boyar, Lene M. Favrholdt:
  Scheduling Jobs on Grid Processors. 17-28
  
• Leah Epstein, Thomas Erlebach, Asaf Levin:
  Variable Sized Online Interval Coloring with Bandwidth. 29-40
  
• Haim Kaplan, Yahav Nussbaum:
  A Simpler Linear-Time Recognition of Circular-Arc Graphs. 41-52
  
• Deepak Ajwani, Tobias Friedrich, Ulrich Meyer:
  An O(n^2.75) Algorithm for Online Topological Ordering. 53-64
  
• David J. Abraham, Telikepalli Kavitha:
  Dynamic Matching Markets and Voting Paths. 65-76
  
• Gianni Franceschini:
  Sorting by Merging or Merging by Sorting? 77-89
  
• Haim Kaplan, Ely Porat, Nira Shafrir:
  Finding the Position of the k-Mismatch and Approximate Tandem Repeats. 90-101
  
• Benjamin Doerr, Tobias Friedrich, Christian Klein, Ralf Osbild:
  Unbiased Matrix Rounding. 102-112
  
• Michael H. Goldwasser, Mark Pedigo:
  Online, Non-preemptive Scheduling of Equal-Length Jobs on Two Identical Machines. 113-123
  
• Leah Epstein, Rob van Stee, Tami Tamir:
  Paging with Request Sets. 124-135
  
• Birgit Heydenreich, Rudolf Müller, Marc Uetz:
  Decentralization and Mechanism Design for Online Machine Scheduling. 136-147
  
• Serge Gaspers, Dieter Kratsch, Mathieu Liedloff:
  Exponential Time Algorithms for the Minimum Dominating Set Problem on Some Graph Classes. 148-159
  
• Igor Razgon:
  Exact Computation of Maximum Induced Forest. 160-171
  
• Frederic Dorn, Fedor V. Fomin, Dimitrios M. Thilikos:
  Fast Subexponential Algorithm for Non-local Problems on Graphs of Bounded Genus. 172-183
  
• Hans-Joachim Böckenhauer, Juraj Hromkovic, Joachim Kneis, Joachim Kupke:
  On the Approximation Hardness of Some Generalizations of TSP. 184-195
  
• Giorgio Ausiello, Bruno Escoffier, Jérôme Monnot, Vangelis Th. Paschos:
  Reoptimization of Minimum and Maximum Traveling Salesman's Tours. 196-207
  
• Spyros Angelopoulos:
  The Node-Weighted Steiner Problem in Graphs of Restricted Node Weights. 208-219
  
• Matthew J. Katz, Gabriel S. Roisman:
  On Guarding Rectilinear Domains. 220-231
  
• Christian Knauer, Andreas Spillner:
  Approximation Algorithms for the Minimum Convex Partition Problem. 232-241
  
• Matthias Müller-Hannemann, Anna Schulze:
  Approximation of Octilinear Steiner Trees Constrained by Hard and Soft Obstacles. 242-254
  
• Frank Kammer:
  Simultaneous Embedding with Two Bends per Edge in Polynomial Area. 255-267
  
• Eyal Ackerman, Kevin Buchin, Christian Knauer, Günter Rote:
  Acyclic Orientation of Drawings. 268-279
  
• Andris Ambainis, Kazuo Iwama, Akinori Kawachi, Rudy Raymond Harry Putra, Shigeru Yamashita:
  Improved Algorithms for Quantum Identification of Boolean Oracles. 280-291
  
• Jan Arpe, Bodo Manthey:
  Approximability of Minimum AND-Circuits. 292-303
  
• Venkatesh Raman, Saket Saurabh:
  Triangles, 4-Cycles and Parameterized (In-)Tractability. 304-315
  
• Erik Jan van Leeuwen:
  Better Approximation Schemes for Disk Graphs. 316-327
  
• Vincenzo Bonifaci, Peter Korteweg, Alberto Marchetti-Spaccamela, Leen Stougie:
  An Approximation Algorithm for the Wireless Gathering Problem. 328-338
  
• Michael Dom, Jiong Guo, Rolf Niedermeier, Sebastian Wernicke:
  Minimum Membership Set Covering and the Consecutive Ones Property. 339-350
  
• José R. Correa, Cristina G. Fernandes, Yoshiko Wakabayashi:
  Approximating Rational Objectives Is as Easy as Approximating Linear Ones. 351-362
  
• Henrik Blunck, Jan Vahrenhold:
  In-Place Algorithms for Computing (Layers of) Maxima. 363-374
  
• Maarten Löffler, Marc J. van Kreveld:
  Largest and Smallest Tours and Convex Hulls for Imprecise Points. 375-387
  
• Joachim Gudmundsson, Michiel H. M. Smid:
  On Spanners of Geometric Graphs. 388-399
  
• Josiah Carlson, David Eppstein:
  The Weighted Maximum-Mean Subtree and Other Bicriterion Subtree Problems. 400-410
  
• Maw-Shang Chang, Ming-Tat Ko, Hsueh-I Lu:
  Linear-Time Algorithms for Tree Root Problems. 411-422
  
• Andreas Brandstädt, Feodor F. Dragan, Yang Xiang, Chenyu Yan:
  Generalized Powers of Graphs and Their Algorithmic Use. 423-434