Skip to main content
SpringerLink
Log in
Book cover

Structural Information and Communication Complexity

21st International Colloquium, SIROCCO 2014, Takayama, Japan, July 23-25, 2014, Proceedings

  • Conference proceedings
  • © 2014

Overview

Editors:
  1. Magnús M. Halldórsson

    1. School of Computer Science, Reykjavik University, Reykjavik, Iceland

    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 8576)

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

Included in the following conference series:

Conference proceedings info: SIROCCO 2014.

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 (27 papers)

  1. Front Matter

    Download chapter PDF

  2. Invited Presentations

    1. Algorithmic Aspects of Resource Management in the Cloud

      • Sebastian Kniesburges, Christine Markarian, Friedhelm Meyer auf der Heide, Christian Scheideler
      Pages 1-13

    2. Communication Complexity Lower Bounds in Distributed Message-Passing

      • Rotem Oshman
      Pages 14-17

    3. Distributed Algorithmic Foundations of Dynamic Networks

      • Gopal Pandurangan
      Pages 18-22

  3. Best Student Paper

    1. The Beachcombers’ Problem: Walking and Searching with Mobile Robots

      • Jurek Czyzowicz, Leszek Gąsieniec, Konstantinos Georgiou, Evangelos Kranakis, Fraser MacQuarrie
      Pages 23-36

  4. Shared Memory and Multiparty Communication

    1. Reliable Shared Memory Abstraction on Top of Asynchronous Byzantine Message-Passing Systems

      • Damien Imbs, Sergio Rajsbaum, Michel Raynal, Julien Stainer
      Pages 37-53

    2. Distributed Transactional Contention Management as the Traveling Salesman Problem

      • Bo Zhang, Binoy Ravindran, Roberto Palmieri
      Pages 54-67

    3. The Complexity Gap between Consensus and Safe-Consensus

      • Rodolfo Conde, Sergio Rajsbaum
      Pages 68-82

    4. The Simultaneous Number-in-Hand Communication Model for Networks: Private Coins, Public Coins and Determinism

      • Florent Becker, Pedro Montealegre, Ivan Rapaport, Ioan Todinca
      Pages 83-95

  5. Network Optimization

    1. Approximation of the Degree-Constrained Minimum Spanning Hierarchies

      • Miklós Molnár, Sylvain Durand, Massinissa Merabet
      Pages 96-107

    2. Secluded Path via Shortest Path

      • Matthew P. Johnson, Ou Liu, George Rabanca
      Pages 108-120

  6. CONGEST Algorithms and Lower Bounds

    1. Distributed Approximation of Minimum Routing Cost Trees

      • Alexandra Hochuli, Stephan Holzer, Roger Wattenhofer
      Pages 121-136

    2. Randomized Lower Bound for Distributed Spanning-Tree Verification

      • Taisuke Izumi
      Pages 137-148

    3. Lessons from the Congested Clique Applied to MapReduce

      • James W. Hegeman, Sriram V. Pemmaraju
      Pages 149-164

  7. Wireless networks

    1. Oblivious Rendezvous in Cognitive Radio Networks

      • Zhaoquan Gu, Qiang-Sheng Hua, Yuexuan Wang, Francis Chi Moon Lau
      Pages 165-179

    2. Local Broadcasting with Arbitrary Transmission Power in the SINR Model

      • Fabian Fuchs, Dorothea Wagner
      Pages 180-193

  8. Aggregation and Creation Games in Networks

    1. Continuous Aggregation in Dynamic Ad-Hoc Networks

      • Sebastian Abshoff, Friedhelm Meyer auf der Heide
      Pages 194-209

    2. Network Creation Games with Traceroute-Based Strategies

      • Davide Bilò, Luciano Gualà, Stefano Leucci, Guido Proietti
      Pages 210-223

  9. Patrolling and Barrier Coverage

    1. Patrolling by Robots Equipped with Visibility

      • Jurek Czyzowicz, Evangelos Kranakis, Dominik Pajak, Najmeh Taleb
      Pages 224-234

    2. Distributed Barrier Coverage with Relocatable Sensors

      • Mohsen Eftekhari, Paola Flocchini, Lata Narayanan, Jaroslav Opatrny, Nicola Santoro
      Pages 235-249
Back to top

Other volumes

  1. Structural Information and Communication Complexity

Keywords

About this book

This book constitutes the refereed proceedings of the 21st International Colloquium on Structural Information and Communication Complexity, SIROCCO 2014, held in Takayama, Japan, in July 2014. The 24 full papers presented together with 5 invited talks were carefully reviewed and selected from 51 submissions. The focus of the colloquium is on following subjects Shared Memory and Multiparty Communication, Network Optimization, CONGEST Algorithms and Lower Bounds, Wireless networks, Aggregation and Creation Games in Networks, Patrolling and Barrier Coverage, Exploration, Rendevous and Mobile Agents.

Editors and Affiliations

  • School of Computer Science, Reykjavik University, Reykjavik, Iceland

    Magnús M. Halldórsson

Bibliographic Information

Publish with us

Policies and ethics

Back to top

Search

Navigation