STACS 2004

Table of Contents

1. Altmetric Badge
   Book Overview
2. Altmetric Badge
   Chapter 1 Approximation Schemes for Metric Clustering Problems
3. Altmetric Badge
   Chapter 2 Positional Determinacy of Infinite Games
4. Altmetric Badge
   Chapter 3 Individual Communication Complexity
5. Altmetric Badge
   Chapter 4 The Complexity of Satisfiability Problems over Finite Lattices
6. Altmetric Badge
   Chapter 5 Constant Width Planar Computation Characterizes ACC 0
7. Altmetric Badge
   Chapter 6 A Simple and Fast Approach for Solving Problems on Planar Graphs
8. Altmetric Badge
   Chapter 7 Sum-Multicoloring on Paths
9. Altmetric Badge
   Chapter 8 Matching Algorithms Are Fast in Sparse Random Graphs
10. Altmetric Badge
    Chapter 9 Algebraic Results on Quantum Automata
11. Altmetric Badge
    Chapter 10 Quantum Identification of Boolean Oracles
12. Altmetric Badge
    Chapter 11 Local Limit Distributions in Pattern Statistics: Beyond the Markovian Models
13. Altmetric Badge
    Chapter 12 A Discontinuity in Pattern Inference
14. Altmetric Badge
    Chapter 13 Algorithms for SAT Based on Search in Hamming Balls
15. Altmetric Badge
    Chapter 14 Identifying Efficiently Solvable Cases of Max CSP
16. Altmetric Badge
    Chapter 15 The Complexity of Boolean Constraint Isomorphism
17. Altmetric Badge
    Chapter 16 On Minimizing the Total Weighted Tardiness on a Single Machine
18. Altmetric Badge
    Chapter 17 Online Competitive Algorithms for Maximizing Weighted Throughput of Unit Jobs
19. Altmetric Badge
    Chapter 18 Optimal and Online Preemptive Scheduling on Uniformly Related Machines
20. Altmetric Badge
    Chapter 19 Parallel Prefetching and Caching Is Hard
21. Altmetric Badge
    Chapter 20 Strongly Stable Matchings in Time O ( nm ) and Extension to the Hospitals-Residents Problem
22. Altmetric Badge
    Chapter 21 Approximation Algorithms for Minimizing Average Distortion
23. Altmetric Badge
    Chapter 22 Digraphs Exploration with Little Memory
24. Altmetric Badge
    Chapter 23 Approximate Path Coloring with Applications to Wavelength Assignment in WDM Optical Networks
25. Altmetric Badge
    Chapter 24 An Algorithmic View on OVSF Code Assignment
26. Altmetric Badge
    Chapter 25 The Syntactic Graph of a Sofic Shift
27. Altmetric Badge
    Chapter 26 Periodicity and Unbordered Words
28. Altmetric Badge
    Chapter 27 Desert Automata and the Finite Substitution Problem
29. Altmetric Badge
    Chapter 28 Satisfiability Problems Complete for Deterministic Logarithmic Space
30. Altmetric Badge
    Chapter 29 A Logspace Approximation Scheme for the Shortest Path Problem for Graphs with Bounded Independence Number
31. Altmetric Badge
    Chapter 30 The Minimal Logically-Defined NP-Complete Problem
32. Altmetric Badge
    Chapter 31 Solving the 2-Disjoint Paths Problem in Nearly Linear Time
33. Altmetric Badge
    Chapter 32 Simpler Computation of Single-Source Shortest Paths in Linear Average Time
34. Altmetric Badge
    Chapter 33 Lattices with Many Cycles Are Dense
35. Altmetric Badge
    Chapter 34 Automata-Based Analysis of Recursive Cryptographic Protocols
36. Altmetric Badge
    Chapter 35 On Minimum Circular Arrangement
37. Altmetric Badge
    Chapter 36 Integral Symmetric 2-Commodity Flows
38. Altmetric Badge
    Chapter 37 Efficient Algorithms for Low-Energy Bounded-Hop Broadcast in Ad-Hoc Wireless Networks
39. Altmetric Badge
    Chapter 38 On the Expressiveness of Deterministic Transducers over Infinite Trees
40. Altmetric Badge
    Chapter 39 Definability and Regularity in Automatic Structures
41. Altmetric Badge
    Chapter 40 Active Context-Free Games
42. Altmetric Badge
    Chapter 41 Worst Case Performance of an Approximation Algorithm for Asymmetric TSP
43. Altmetric Badge
    Chapter 42 On Visibility Representation of Plane Graphs
44. Altmetric Badge
    Chapter 43 Topology Matters: Smoothed Competitiveness of Metrical Task Systems
45. Altmetric Badge
    Chapter 44 A Randomized Competitive Algorithm for Evaluating Priced AND/OR Trees
46. Altmetric Badge
    Chapter 45 The Plurality Problem with Three Colors
47. Altmetric Badge
    Chapter 46 A Measured Collapse of the Modal μ -Calculus Alternation Hierarchy
48. Altmetric Badge
    Chapter 47 An Information Theoretic Lower Bound for Broadcasting in Radio Networks
49. Altmetric Badge
    Chapter 48 A New Model for Selfish Routing
50. Altmetric Badge
    Chapter 49 Broadcast in the Rendezvous Model
51. Altmetric Badge
    Chapter 50 Time-Space Tradeoff in Derandomizing Probabilistic Logspace
52. Altmetric Badge
    Chapter 51 What Can be Efficiently Reduced to the K-Random Strings?
53. Altmetric Badge
    Chapter 52 Regular Language Matching and Other Decidable Cases of the Satisfiability Problem for Constraints between Regular Open Terms
54. Altmetric Badge
    Chapter 53 Deterministic Truthful Approximation Mechanisms for Scheduling Related Machines
55. Altmetric Badge
    Chapter 54 The Expected Competitive Ratio for Weighted Completion Time Scheduling
56. Altmetric Badge
    Chapter 55 Effective Strong Dimension in Algorithmic Information and Computational Complexity
57. Altmetric Badge
    Chapter 56 A Lower Bound on the Competitive Ratio of Truthful Auctions
58. Altmetric Badge
    Chapter 57 Errata to Analysis of the Harmonic Algorithm for Three Servers