Algorithms and Complexity
Springer Berlin (Verlag)
978-3-642-13072-4 (ISBN)
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 ParameterizedRoute 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.
Erscheint lt. Verlag | 20.5.2010 |
---|---|
Reihe/Serie | Lecture Notes in Computer Science | Theoretical Computer Science and General Issues |
Zusatzinfo | XI, 384 p. |
Verlagsort | Berlin |
Sprache | englisch |
Gewicht | 596 g |
Themenwelt | Mathematik / Informatik ► Informatik |
Schlagworte | Algorithm analysis and problem complexity • algorithms • Approximation • combinatorial optimization • combinatorics • Complexity • Computational Complexity • Computational Geometry • Computational Graph Theory • data structures • Game Theory • geometric algorithms • Graph Algorithms • graph coloring • Graph Computations • networ • network algorithms • Routing • Scheduling • String Algorithms • tree algorithms • tree decompositions |
ISBN-10 | 3-642-13072-0 / 3642130720 |
ISBN-13 | 978-3-642-13072-4 / 9783642130724 |
Zustand | Neuware |
Haben Sie eine Frage zum Produkt? |
aus dem Bereich