IFIP TC6 Open Digital Library

4. IFIP TCS 2006: Santiago, Chile

Fourth IFIP International Conference on Theoretical Computer Science (TCS 2006), IFIP 19th World Computer Congress, TC-1 Foundations of Computer Science, August 23-24, 2006, Santiago, Chile

Gonzalo Navarro, Leopoldo E. Bertossi, Yoshiharu Kohayakawa

Springer, IFIP 209, ISBN: 0-387-34633-3


Invited Talks

Locality of Queries and Transformations.

Marcelo Arenas


From Informatics to Quantum Informatics.

Jozef Gruska


RDF as a Data Model.

Claudio Gutiérrez


Adversarial Queueing Theory Revisited.

Marcos A. Kiwi


Distributed Algorithms for Autonomous Mobile Robots.

Nicola Santoro


Recursion and Probability.

Mihalis Yannakakis


Invited Papers

From Informatics to Quantum Informatics.

Jozef Gruska


Distributed Algorithms for Autonomous Mobile Robots.

Giuseppe Prencipe, Nicola Santoro


Contributed Papers

The Unsplittable Stable Marriage Problem.

Brian C. Dean, Michel X. Goemans, Nicole Immorlica


Variations on an Ordering Theme with Constraints.

Walter Guttmann, Markus Maucher


BuST-Bundled Suffix Trees.

Luca Bortolussi, Francesco Fabris, Alberto Policriti


An O(1) Solution to the Prefix Sum Problem on a Specialized Memory Architecture.

Andrej Brodnik, Johan Karlsson, J. Ian Munro, Andreas Nilsson


An Algorithm to Reduce the Communication Traffic for Multi-Word Searches in a Distributed Hash Table.

Yuichi Sei, Kazutaka Matsuzaki, Shinichi Honiden


Exploring an Unknown Graph to Locate a Black Hole Using Tokens.

Stefan Dobrev, Paola Flocchini, Rastislav Kralovic, Nicola Santoro


Fast Cellular Automata with Restricted Inter-Cell Communication: Computational Capacity.

Martin Kutrib, Andreas Malcher


Asynchonous Distributed Components: Concurrency and Determinacy.

Denis Caromel, Ludovic Henrio


Decidable Properties for Regular Cellular Automata.

Pietro di Lena


Symbolic Determinisation of Extended Automata.

Thierry Jéron, Hervé Marchand, Vlad Rusu


Regular Hedge Model Checking.

Julien d'Orso, Tayssir Touili


Completing Categorical Algebras.

Stephen L. Bloom, Zoltán Ésik


Reusing Optimal TSP Solutions for Locally Modified Input Instances.

Hans-Joachim Böckenhauer, Luca Forlizzi, Juraj Hromkovic, Joachim Kneis, Joachim Kupke, Guido Proietti, Peter Widmayer


Spectral Partitioning of Random Graphs with Given Expected Degrees.

Amin Coja-Oghlan, Andreas Goerdt, André Lanka


A Connectivity Rating for Vertices in Networks.

Marco Abraham, Rolf Kötter, Antje Krumnack, Egon Wanke


On PTAS for Planar Graph Problems.

Xiuzhen Huang, Jianer Chen