Claire Kenyon (auth.), Volker Diekert, Michel Habib (eds.)3540212361, 9783540247494, 9783540212362
The 54 revised full papers presented together with two invited contributions were carefully reviewed and selected from more than 200 submissions. The papers are organized in topical sections on structural complexity, graph algorithms, quantum computing, satisfiability – constraint satisfaction problems, scheduling, algorithms, networks, automata theory and words, path algorithms, cryptography, logic and formal languages, game theory and complexity, and algorithmic information.
Table of contents :
Front Matter….Pages –
Approximation Schemes for Metric Clustering Problems….Pages 1-3
Positional Determinacy of Infinite Games….Pages 4-18
Individual Communication Complexity….Pages 19-30
The Complexity of Satisfiability Problems over Finite Lattices….Pages 31-43
Constant Width Planar Computation Characterizes ACC 0 ….Pages 44-55
A Simple and Fast Approach for Solving Problems on Planar Graphs….Pages 56-67
Sum-Multicoloring on Paths….Pages 68-80
Matching Algorithms Are Fast in Sparse Random Graphs….Pages 81-92
Algebraic Results on Quantum Automata….Pages 93-104
Quantum Identification of Boolean Oracles….Pages 105-116
Local Limit Distributions in Pattern Statistics: Beyond the Markovian Models….Pages 117-128
A Discontinuity in Pattern Inference….Pages 129-140
Algorithms for SAT Based on Search in Hamming Balls….Pages 141-151
Identifying Efficiently Solvable Cases of Max CSP….Pages 152-163
The Complexity of Boolean Constraint Isomorphism….Pages 164-175
On Minimizing the Total Weighted Tardiness on a Single Machine….Pages 176-186
Online Competitive Algorithms for Maximizing Weighted Throughput of Unit Jobs….Pages 187-198
Optimal and Online Preemptive Scheduling on Uniformly Related Machines….Pages 199-210
Parallel Prefetching and Caching Is Hard….Pages 211-221
Strongly Stable Matchings in Time O ( nm ) and Extension to the Hospitals-Residents Problem….Pages 222-233
Approximation Algorithms for Minimizing Average Distortion….Pages 234-245
Digraphs Exploration with Little Memory….Pages 246-257
Approximate Path Coloring with Applications to Wavelength Assignment in WDM Optical Networks….Pages 258-269
An Algorithmic View on OVSF Code Assignment….Pages 270-281
The Syntactic Graph of a Sofic Shift….Pages 282-293
Periodicity and Unbordered Words….Pages 294-304
Desert Automata and the Finite Substitution Problem….Pages 305-316
Satisfiability Problems Complete for Deterministic Logarithmic Space….Pages 317-325
A Logspace Approximation Scheme for the Shortest Path Problem for Graphs with Bounded Independence Number….Pages 326-337
The Minimal Logically-Defined NP-Complete Problem….Pages 338-349
Solving the 2-Disjoint Paths Problem in Nearly Linear Time….Pages 350-361
Simpler Computation of Single-Source Shortest Paths in Linear Average Time….Pages 362-369
Lattices with Many Cycles Are Dense….Pages 370-381
Automata-Based Analysis of Recursive Cryptographic Protocols….Pages 382-393
On Minimum Circular Arrangement….Pages 394-405
Integral Symmetric 2-Commodity Flows….Pages 406-417
Efficient Algorithms for Low-Energy Bounded-Hop Broadcast in Ad-Hoc Wireless Networks….Pages 418-427
On the Expressiveness of Deterministic Transducers over Infinite Trees….Pages 428-439
Definability and Regularity in Automatic Structures….Pages 440-451
Active Context-Free Games….Pages 452-464
Worst Case Performance of an Approximation Algorithm for Asymmetric TSP….Pages 465-476
On Visibility Representation of Plane Graphs….Pages 477-488
Topology Matters: Smoothed Competitiveness of Metrical Task Systems….Pages 489-500
A Randomized Competitive Algorithm for Evaluating Priced AND/OR Trees….Pages 501-512
The Plurality Problem with Three Colors….Pages 513-521
A Measured Collapse of the Modal μ -Calculus Alternation Hierarchy….Pages 522-533
An Information Theoretic Lower Bound for Broadcasting in Radio Networks….Pages 534-546
A New Model for Selfish Routing….Pages 547-558
Broadcast in the Rendezvous Model….Pages 559-570
Time-Space Tradeoff in Derandomizing Probabilistic Logspace….Pages 571-583
What Can be Efficiently Reduced to the K-Random Strings?….Pages 584-595
Regular Language Matching and Other Decidable Cases of the Satisfiability Problem for Constraints between Regular Open Terms….Pages 596-607
Deterministic Truthful Approximation Mechanisms for Scheduling Related Machines….Pages 608-619
The Expected Competitive Ratio for Weighted Completion Time Scheduling….Pages 620-631
Effective Strong Dimension in Algorithmic Information and Computational Complexity….Pages 632-643
A Lower Bound on the Competitive Ratio of Truthful Auctions….Pages 644-655
Errata to Analysis of the Harmonic Algorithm for Three Servers….Pages 656-656
Back Matter….Pages –
Reviews
There are no reviews yet.