Algorithm Theory - SWAT 2006

Table of Contents

1. Altmetric Badge
   Book Overview
2. Altmetric Badge
   Chapter 1 Top-Down Analysis of Path Compression: Deriving the Inverse-Ackermann Bound Naturally (and Easily)
3. Altmetric Badge
   Chapter 2 Results and Problems on Self-adjusting Search Trees and Related Data Structures
4. Altmetric Badge
   Chapter 3 Classic and Quantum Network Coding
5. Altmetric Badge
   Chapter 4 Multiplexing Packets with Arbitrary Deadlines in Bounded Buffers
6. Altmetric Badge
   Chapter 5 Scheduling Jobs on Grid Processors
7. Altmetric Badge
   Chapter 6 Variable Sized Online Interval Coloring with Bandwidth
8. Altmetric Badge
   Chapter 7 A Simpler Linear-Time Recognition of Circular-Arc Graphs
9. Altmetric Badge
   Chapter 8 An ${\cal O}(n^{2.75})$ Algorithm for Online Topological Ordering
10. Altmetric Badge
    Chapter 9 Dynamic Matching Markets and Voting Paths
11. Altmetric Badge
    Chapter 10 Sorting by Merging or Merging by Sorting?
12. Altmetric Badge
    Chapter 11 Finding the Position of the k -Mismatch and Approximate Tandem Repeats
13. Altmetric Badge
    Chapter 12 Unbiased Matrix Rounding
14. Altmetric Badge
    Chapter 13 Online, Non-preemptive Scheduling of Equal-Length Jobs on Two Identical Machines
15. Altmetric Badge
    Chapter 14 Paging with Request Sets
16. Altmetric Badge
    Chapter 15 Decentralization and Mechanism Design for Online Machine Scheduling
17. Altmetric Badge
    Chapter 16 Exponential Time Algorithms for the Minimum Dominating Set Problem on Some Graph Classes
18. Altmetric Badge
    Chapter 17 Exact Computation of Maximum Induced Forest
19. Altmetric Badge
    Chapter 18 Fast Subexponential Algorithm for Non-local Problems on Graphs of Bounded Genus
20. Altmetric Badge
    Chapter 19 On the Approximation Hardness of Some Generalizations of TSP
21. Altmetric Badge
    Chapter 20 Reoptimization of Minimum and Maximum Traveling Salesman’s Tours
22. Altmetric Badge
    Chapter 21 The Node-Weighted Steiner Problem in Graphs of Restricted Node Weights
23. Altmetric Badge
    Chapter 22 On Guarding Rectilinear Domains
24. Altmetric Badge
    Chapter 23 Approximation Algorithms for the Minimum Convex Partition Problem
25. Altmetric Badge
    Chapter 24 Approximation of Octilinear Steiner Trees Constrained by Hard and Soft Obstacles
26. Altmetric Badge
    Chapter 25 Simultaneous Embedding with Two Bends per Edge in Polynomial Area
27. Altmetric Badge
    Chapter 26 Acyclic Orientation of Drawings
28. Altmetric Badge
    Chapter 27 Improved Algorithms for Quantum Identification of Boolean Oracles
29. Altmetric Badge
    Chapter 28 Approximability of Minimum AND-Circuits
30. Altmetric Badge
    Chapter 29 Triangles, 4-Cycles and Parameterized (In-)Tractability
31. Altmetric Badge
    Chapter 30 Better Approximation Schemes for Disk Graphs
32. Altmetric Badge
    Chapter 31 An Approximation Algorithm for the Wireless Gathering Problem
33. Altmetric Badge
    Chapter 32 Minimum Membership Set Covering and the Consecutive Ones Property
34. Altmetric Badge
    Chapter 33 Approximating Rational Objectives Is as Easy as Approximating Linear Ones
35. Altmetric Badge
    Chapter 34 In-Place Algorithms for Computing (Layers of) Maxima
36. Altmetric Badge
    Chapter 35 Largest and Smallest Tours and Convex Hulls for Imprecise Points
37. Altmetric Badge
    Chapter 36 On Spanners of Geometric Graphs
38. Altmetric Badge
    Chapter 37 The Weighted Maximum-Mean Subtree and Other Bicriterion Subtree Problems
39. Altmetric Badge
    Chapter 38 Linear-Time Algorithms for Tree Root Problems
40. Altmetric Badge
    Chapter 39 Generalized Powers of Graphs and Their Algorithmic Use