Algorithms and Complexity 7th International Conference, CIAC 2010, Rome, Italy, May 26-28, 2010. Proceedings /

Corporate Author: SpringerLink (Online service)
Other Authors: Calamoneri, Tiziana., Diaz, Josep.
Format: Electronic
Language: English
Published: Berlin, Heidelberg : Springer Berlin Heidelberg, 2010.
Series: Lecture Notes in Computer Science, 6078
Online Access:
Tags: Add Tag
No Tags, Be the first to tag this record!
Table of Contents:
  • 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.