Skip to main content
SpringerLink
Log in
Book cover

Structural Information and Communication Complexity

16th International Colloquium, SIROCCO 2009, Piran, Slovenia, May 25-27, 2009, Revised Selected Papers

  • Conference proceedings
  • © 2010

Overview

Editors:
  1. Shay Kutten

    1. Technion – Israel Institute of Technology, Dept. of Industrial Engineering and Management,, Technion City, 32000, Israel

    View editor publications

    You can also search for this editor in PubMed   Google Scholar

  2. Janez Žerovnik

    1. Faculty of Mechanical Engineering, University of Maribor, Maribor, Slovenia

    View editor publications

    You can also search for this editor in PubMed   Google Scholar

Part of the book series: Lecture Notes in Computer Science (LNCS, volume 5869)

Part of the book sub series: Theoretical Computer Science and General Issues (LNTCS)

Included in the following conference series:

Conference proceedings info: SIROCCO 2009.

This is a preview of subscription content, log in via an institution to check access.

Access this book

Log in via an institution
eBook USD 39.99
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book USD 54.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Other ways to access

Licence this eBook for your library

Institutional subscriptions

Table of contents (25 papers)

  1. Front Matter

    Download chapter PDF

  2. Invited Talks

    1. Zooming in on Network-on-Chip Architectures

      • Israel Cidon
      Pages 1-1

    2. On Efficient Gossiping in Radio Networks

      • Leszek Gąsieniec
      Pages 2-14

  3. Regular Papers

    1. Regular Register: An Implementation in a Churn Prone Environment

      • Roberto Baldoni, Silvia Bonomi, Michel Raynal
      Pages 15-29

    2. Ordered Coloring Grids and Related Graphs

      • Amotz Bar-Noy, Panagiotis Cheilaris, Michael Lampis, Valia Mitsou, Stathis Zachos
      Pages 30-43

    3. Sub-linear Universal Spatial Gossip Protocols

      • Hervé Baumann, Pierre Fraigniaud
      Pages 44-56

    4. Designing Hypergraph Layouts to GMPLS Routing Strategies

      • Jean-Claude Bermond, David Coudert, Joanna Moulierac, Stéphane Pérennes, Ignasi Sau, Fernando Solano Donado
      Pages 57-71

    5. On Gossip and Populations

      • Marin Bertier, Yann Busnel, Anne-Marie Kermarrec
      Pages 72-86

    6. Reconstructing Visibility Graphs with Simple Robots

      • Davide Bilò, Yann Disser, Matúš Mihalák, Subhash Suri, Elias Vicari, Peter Widmayer
      Pages 87-99

    7. Stability of Networks in Stretchable Graphs

      • Davide Bilò, Michael Gatto, Luciano Gualà, Guido Proietti, Peter Widmayer
      Pages 100-112

    8. Space Complexity of Self-stabilizing Leader Election in Passively-Mobile Anonymous Agents

      • Shukai Cai, Taisuke Izumi, Koichi Wada
      Pages 113-125

    9. Characterizing Topological Assumptions of Distributed Algorithms in Dynamic Networks

      • Arnaud Casteigts, Serge Chaumette, Afonso Ferreira
      Pages 126-140

    10. A New Polynomial Silent Stabilizing Spanning-Tree Construction Algorithm

      • Alain Cournier
      Pages 141-153

    11. Spatial Node Distribution of Manhattan Path Based Random Waypoint Mobility Models with Applications

      • Pilu Crescenzi, Miriam Di Ianni, Andrea Marino, Gianluca Rossi, Paola Vocca
      Pages 154-166

    12. More Efficient Periodic Traversal in Anonymous Undirected Graphs

      • Jurek Czyzowicz, Stefan Dobrev, Leszek Gąsieniec, David Ilcinkas, Jesper Jansson, Ralf Klasing et al.
      Pages 167-181

    13. Black Hole Search in Directed Graphs

      • Jurek Czyzowicz, Stefan Dobrev, Rastislav Královič, Stanislav Miklík, Dana Pardubská
      Pages 182-194

    14. Optimal Probabilistic Ring Exploration by Semi-synchronous Oblivious Robots

      • Stéphane Devismes, Franck Petit, Sébastien Tixeuil
      Pages 195-208

    15. Revisiting Randomized Parallel Load Balancing Algorithms

      • Guy Even, Moti Medina
      Pages 209-221

    16. An Improved Strategy for Exploring a Grid Polygon

      • Agnieszka Kolenderska, Adrian Kosowski, Michał Małafiejski, Paweł Żyliński
      Pages 222-236

    17. An Efficient Self-stabilizing Distance-2 Coloring Algorithm

      • Jean Blair, Fredrik Manne
      Pages 237-251
Back to top

Other volumes

  1. Structural Information and Communication Complexity

Keywords

About this book

This book constitutes the thoroughly refereed post-conference proceedings of the 16th International Colloquium on Structural Information and Communication Complexity, SIROCCO 2009, held in Piran, Slovenia, in May 2009.

The 23 revised full papers presented were carefully reviewed and selected from 53 submissions. The volume also contains two invited papers. SIROCCO addresses topics such as distributed computing, parallel computing, game theory, social networks, networking, mobile computing, peer to peer systems, communication complexity, combinatorial optimization; special focus is put to compact data structures, information dissemination, informative labeling schemes, distributed scheduling, wireless networks and scheduling of transmissions, routing, broadcasting, and localization.

Editors and Affiliations

  • Technion – Israel Institute of Technology, Dept. of Industrial Engineering and Management,, Technion City, 32000, Israel

    Shay Kutten

  • Faculty of Mechanical Engineering, University of Maribor, Maribor, Slovenia

    Janez Žerovnik

Bibliographic Information

Publish with us

Policies and ethics

Back to top

Search

Navigation