Limit search to available items
Book Cover
E-book
Author Italian Conference on Algorithms and Complexity (7th : 2010 : Rome, Italy)

Title Algorithms and complexity : 7th international conference, CIAC 2010, Rome, Italy, May 26-28, 2010 : proceedings / Tiziana Calamoneri, Josep Diaz (eds.)
Published Berlin ; New York : Springer, ©2010

Copies

Description 1 online resource (xi, 384 pages) : illustrations
Series Lecture notes in computer science, 0302-9743 ; 6078
LNCS sublibrary: SL 1-theoretical computer science and general issues
Lecture notes in computer science ; 6078.
LNCS sublibrary. SL 1, Theoretical computer science and general issues.
Contents Invited talks: Towards a distributed search engine / Ricardo Baeza-Yates -- Mechanisms for the marriage and the assignment game / Paul Dutting and Monika Henzinger -- Resilient algorithms and data structures / Giuseppe F. Italiano -- Session 1 : graph algorithms I. An exact algorithm for connected red-blue dominating set / Faisal N. Abu-Khzam, Amer E. Mouawad, and Mathieu Liedloff -- Maximizing PageRank with new backlinks / Martin Olsen -- Enumerating rooted graphs with reflectional block structures / Bingbing Zhuang and Hiroshi Nagamochi -- Improved approximations for TSP with simple precedence constraints (extended abstract) / Hans-Joachim Böckenhauer, Ralf Klasing, Tobias Mömke, and Monika Steinová -- Polynomial space algorithms for counting dominating sets and the domatic number / Johan M.M. van Rooij -- Session 2 : computational complexity. Parameterized complexity of even/odd subgraph problems / Leizhen Cai and Boting Yang -- Popular matchings in the marriage and roommates problems / Péter Biró, Robert W. Irving, and David F. Manlove -- Bounding the number of tolerable faults in majority-based systems / Ching-Lueh Chang and Yuh-Dauh Lyuu -- A parameterized algorithms for CHORDAL SANDWICH / Pinar Heggernes, Federico Mancini, Jesper Nederlof, and Yngve Villanger -- Testing computability by width-2 OBDDs where the variable order is unknown / Dana Ron and Gilad Tsur -- Session 3 : graph coloring. Graph unique-maximum and conflict-free colorings / Panagiotis Cheilaris and Géza Tóth -- Strategic coloring of a graph / Bruno Escoffier, Laurent Gourvès, and Jérôme Monnot -- Session 4 : tree algorithms and tree decompositions. Multicut algorithms via tree decompositions / Reinhard Pichler, Stefan Rümmele, and Stefan Woltran -- The Steiner tree reoptimization problem with sharpened triangle inequality (extended abstract) / Hans-Joachim Böckenhauer, Karin Freiermuth, Juraj Hromkovic̆, Tobias Mömke, Andreas Sprock, and Björn Steffen -- Kernelization for maximum leaf spanning tree with positive vertex weights / Bart Jansen -- A planar linear arboricity conjecture / Marek Cygan, Łukasz Kowalik, and Borut Luz̆ar -- Session 5 : computational geometry. On the number of higher order Delaunay triangulations / Dieter Mitsche, Maria Saumell, and Rodrigo I. Silveira -- How simple robots benefit from looking back / Jérémie Chalopin, Shantanu Das, Yann Disser, Matús̆ Mihalák, and Peter Widmayer -- Session 6 : game theory. On strategy improvement algorithms for simple stochastic games / Rahul Tripathi, Elena Valkanova, and V.S. Anil Kumar -- Online cooperative cost sharing / Janina Brenner and Guido Schäfer -- Session 7 : graph algorithms II. On the power of nodes of degree four in the local max-cut problem / Burkhard Monien and Tobias Tscheuschner -- Packing bipartite graphs with covers of complete bipartite graphs / Jérémie Chalopin and Daniël Paulusma -- Irredundant set faster than O(2n) / Marek Cygan, Marcin Pilipczuk, and Jakub Onufry Wojtaszczyk -- The complexity of computing minimal unidirectional covering sets / Dorothea Baumeister, Felix Brandt, Felix Fischer, Jan Hoffmann, and Jörg Rothe -- A parameterized route to exact puzzles : breaking the 2n-barrier for irredundance (extended abstract) / Daniel Binkele-Raible, Ljiljana Brankovic, Henning Fernau, Joachim Kneis, Dieter Kratsch, Alexander Langer, Mathieu Liedloff, and Peter Rossmanith -- Session 8 : string algorithms. Finding the maximum suffix with fewer comparisons / Gianni Franceschini and Torben Hagerup -- An algorithmic framework for motif discovery problems in weighted sequences / Hui Zhang, Qing Guo, and Costas S. Iliopoulos -- Session 9 : network algorithms. Capacitated confluent flows : complexity and algorithms / Daniel Dressler and Martin Strehler -- Preprocessing speed-up techniques is hard / Reinhard Bauer, Tobias Columbus, Bastian Katz, Marcus Krug, and Dorothea Wagner -- Communication requirements for stable marriages / Jen-Hou Chou and Chi-Jen Lu
Summary Annotation This book constitutes the refereed proceedings of the 7th International Conference on Algorithms and Computation, CIAC 2010, held in Rome, Italy, in May 2010. The 30 revised full papers presented together with 3 invited papers were carefully reviewed and selected from 114 submissions. Among the topics addressed are graph algorithms I, computational complexity, graph coloring, tree algorithms and tree decompositions, computational geometry, game theory, graph algorithms II, and string algorithms
Bibliography Includes bibliographical references and index
Notes Print version record
Subject Algorithms -- Congresses
Computational complexity -- Congresses
Computer algorithms.
Algorithms.
Algorithms
Computing Methodologies
algorithms.
Algorithmus.
Komplexitätstheorie.
Algorithms.
Computational complexity.
Informatique.
Computer algorithms
Algorithms
Computational complexity
Algorithmus
Komplexitätstheorie
Rom <2010>.
Rom <2010>
Genre/Form proceedings (reports)
Conference papers and proceedings
Conference papers and proceedings.
Actes de congrès.
Form Electronic book
Author Calamoneri, Tiziana.
Díaz, J. (Josep), 1950-
LC no. 2010926487
ISBN 9783642130731
3642130739