+612 9045 4394
Algorithms and Complexity : 7th International Conference, CIAC 2010, Rome, Italy, May 26-28, 2010, Proceedings - Josep Diaz

Algorithms and Complexity

7th International Conference, CIAC 2010, Rome, Italy, May 26-28, 2010, Proceedings

By: Josep Diaz (Editor), Tiziana Calamoneri (Editor)


Published: 20th May 2010
Ships: 5 to 9 business days
5 to 9 business days
or 4 easy payments of $33.88 with Learn more
if ordered within

This volume contains the papers presented at the 7th International Conference onAlgorithmsandComplexity(CIAC-2010), whichtookplaceatSapienza, U- versity of Rome, during May 26-28, 2010. The volume contains 30 accepted papers, selected by the Program Comm- tee from 114 submissions received, with an acceptance ratio of 26%. We thank all the authors who submitted papers, the members of the Program Committee and the external reviewers. We are grateful also to the ?ve invited speakers, Ricardo Baeza-Yates (Yahoo! Research), Eran Halperin (Tel Aviv University), Monika Henzinger (EPF Lausanne), Giuseppe F. Italiano (University of Rome Tor Vergata), and Bruce Reed (McGill University), that kindly accepted our invitation to give plenary lectures at the conference. We gratefully acknowledge support from Sapienza, its Department of Computer Science, Yahoo! Research and EATCS. We ?nally would like to thank Saverio Caminiti, Umberto F- raro Petrillo, Emanuele G. Fusco and M. Daniela Salvati for their help in the organization tasks. March 2010 Tiziana Calamoneri Josep D ?az Conference Organization Steering Committee Giorgio Ausiello Sapienza University of Rome, Italy Giuseppe F.

Invited Talks
Towards a Distributed Search Enginep. 1
Mechanisms for the Marriage and the Assignment Gamep. 6
Resilient Algorithms and Data Structuresp. 13
Graph Algorithms I
An Exact Algorithm for Connected Red-Blue Dominating Setp. 25
Maximizing PageRank with New Backlinksp. 37
Enumerating Rooted Graphs with Reflectional Block Structuresp. 49
Improved Approximations for TSP with Simple Precedence Constraints (Extended Abstract)p. 61
Polynomial Space Algorithms for Counting Dominating Sets and the Domatic Numberp. 73
Computational Complexity
Parameterized Complexity of Even/Odd Subgraph Problemsp. 85
Popular Matchings in the Marriage and Roommated Problemsp. 97
Bounding the Number of Tolerable Faults in Majority-Based Systemsp. 109
A Parameterized Algorithm for Chordal Sandwichp. 120
Testing Computability by Width-2 OBDDs Where the Variable Order is Unknownp. 131
Graph Coloring
Graph Unique-Maximum and Conflict-Free Coloringsp. 143
Strategic Coloring of a Graphp. 155
Tree Algorithms and Tree Decompositions
Multicut Algorithms via Tree Decompositionsp. 167
The Steiner Tree Reoptimization Problem with Sharpened Triangle Inequality (Extended Abstract)p. 180
Kernelization for Maximum Leaf Spanning Tree with Positive Vertex Weightsp. 192
A Planar Linear Arboricity Conjecturep. 204
Computational Geometry
On the Number of Higher Order Delaunay Triangulationsp. 217
How Simple Robots Benefit from Looking Backp. 229
Game Theory
On Strategy Improvement Algorithms for Simple Stochastic Gamesp. 240
Online Cooperative Cost Sharingp. 252
Graph Algorithms II
On the Power of Nodes of Degree Four in the Local Max-Cut Problemp. 264
Packing Bipartite Graphs with Covers of Complete Bipartite Graphsp. 276
Irredundant Set Faster Than O(2n)p. 288
The Complexity of Computing Minimal Unidirectional Covering Setsp. 299
A Parameterized Route to Exact Puzzles: Breaking the 2n-Barrier for Irredundance (Extended Abstract)p. 311
String Algorithms
Finding the Maximum Suffix with Fewer Comparisonsp. 323
An Algorithmic Framework for Motif Discovery Problems in Weighted Sequencesp. 335
Network Algorithms
Capacitated Confluent Flows: Complexity and Algorithmsp. 347
Preprocessing Speed-Up Techniques Is Hardp. 359
Communication Requirements for Stable Marriagesp. 371
Author Indexp. 383
Table of Contents provided by Ingram. All Rights Reserved.

ISBN: 9783642130724
ISBN-10: 3642130720
Series: Lecture Notes in Computer Science
Audience: Professional
Format: Paperback
Language: English
Number Of Pages: 384
Published: 20th May 2010
Publisher: Springer-Verlag Berlin and Heidelberg Gmbh & Co. Kg
Country of Publication: DE
Dimensions (cm): 23.37 x 15.49  x 2.03
Weight (kg): 0.61