Algorithms and Complexity

Inhalt

Invited Talks.- Towards a Distributed Search Engine.- Mechanisms for the Marriage and the Assignment Game.- Resilient Algorithms and Data Structures.- Session 1. Graph Algorithms I.- An Exact Algorithm for Connected Red-Blue Dominating Set.- Maximizing PageRank with New Backlinks.- Enumerating Rooted Graphs with Reflectional Block Structures.- Improved Approximations for TSP with Simple Precedence Constraints.- Polynomial Space Algorithms for Counting Dominating Sets and the Domatic Number.- Session 2. Computational Complexity.- Parameterized Complexity of Even/Odd Subgraph Problems.- Popular Matchings in the Marriage and Roommates Problems.- Bounding the Number of Tolerable Faults in Majority-Based Systems.- A Parameterized Algorithm for Chordal Sandwich.- Testing Computability by Width-2 OBDDs Where the Variable Order is Unknown.- Session 3. Graph Coloring.- Graph Unique-Maximum and Conflict-Free Colorings.- Strategic Coloring of a Graph.- Session 4. Tree Algorithms and Tree Decompositions.- Multicut Algorithms via Tree Decompositions.- The Steiner Tree Reoptimization Problem with Sharpened Triangle Inequality.- Kernelization for Maximum Leaf Spanning Tree with Positive Vertex Weights.- A Planar Linear Arboricity Conjecture.- Session 5. Computational Geometry.- On the Number of Higher Order Delaunay Triangulations.- How Simple Robots Benefit from Looking Back.- Session 6. Game Theory.- On Strategy Improvement Algorithms for Simple Stochastic Games.- Online Cooperative Cost Sharing.- Session 7. Graph Algorithms II.- On the Power of Nodes of Degree Four in the Local Max-Cut Problem.- Packing Bipartite Graphs with Covers of Complete Bipartite Graphs.- Irredundant Set Faster Than O(2 n ).- The Complexity of Computing Minimal Unidirectional Covering Sets.- A Parameterized Route to Exact Puzzles: Breaking the 2 n -Barrier for Irredundance.- Session 8. String Algorithms.- Finding the Maximum Suffix with Fewer Comparisons.- An Algorithmic Framework for Motif Discovery Problems in Weighted Sequences.- Session 9. Network Algorithms.- Capacitated Confluent Flows: Complexity and Algorithms.- Preprocessing Speed-Up Techniques Is Hard.- Communication Requirements for Stable Marriages.