Structural Information and Communication Complexity: 13th International Colloquium, SIROCCO 2006, Chester, UK, July 2-5, 2006. Proceedings

Evangelos Kranakis, Danny Krizanc (auth.), Paola Flocchini, Leszek Gąsieniec (eds.)3540354743, 9783540354741

This book constitutes the refereed proceedings of the 13th International Colloquium on Structural Information and Communication Complexity, SIROCCO 2006, held in Chester, UK, in July 2006.

The 24 revised full papers presented together with 3 invited talks were carefully reviewed and selected from 68 submissions. The papers address issues such as topics in distributed and parallel computing, information dissemination, communication complexity, interconnection networks, high speed networks, wireless and sensor networks, mobile computing, optical computing, autonomous robots, and related areas. The papers are organized in topical sections on robots, routing, distributed algorithms, fault tolerance, radio networks, and self-stabilizing alorgithms.

---

Table of contents :
Front Matter….Pages –
Mobile Agent Rendezvous: A Survey….Pages 1-9
Adapting to Point Contention with Long-Lived Safe Agreement….Pages 10-23
Sensor Networks: Distributed Algorithms Reloaded – or Revolutions?….Pages 24-28
Local Algorithms for Autonomous Robot Systems….Pages 29-43
How to Meet in Anonymous Network….Pages 44-58
Setting Port Numbers for Fast Graph Exploration….Pages 59-69
Distributed Chasing of Network Intruders….Pages 70-84
Election in the Qualitative World….Pages 85-99
Fast Deterministic Distributed Algorithms for Sparse Spanners….Pages 100-114
Efficient Distributed Weighted Matchings on Trees….Pages 115-129
Approximation Strategies for Routing Edge Disjoint Paths in Complete Graphs….Pages 130-142
Short Labels by Traversal and Jumping….Pages 143-156
An Optimal Rebuilding Strategy for a Decremental Tree Problem….Pages 157-170
Optimal Delay for Media-on-Demand with Pre-loading and Pre-buffering….Pages 171-181
Strongly Terminating Early-Stopping k -Set Agreement in Synchronous Systems with General Omission Failures….Pages 182-196
On Fractional Dynamic Faults with Threshold….Pages 197-211
Discovering Network Topology in the Presence of Byzantine Faults….Pages 212-226
Minimum Energy Broadcast and Disk Cover in Grid Wireless Networks….Pages 227-239
3-D Minimum Energy Broadcasting….Pages 240-252
Average-Time Complexity of Gossiping in Radio Networks….Pages 253-267
L(h,1,1)-Labeling of Outerplanar Graphs….Pages 268-279
Combinatorial Algorithms for Compressed Sensing….Pages 280-294
On the Existence of Truthful Mechanisms for the Minimum-Cost Approximate Shortest-Paths Tree Problem….Pages 295-309
Dynamic Asymmetric Communication….Pages 310-318
Approximate Top-k Queries in Sensor Networks….Pages 319-333
Self-stabilizing Space Optimal Synchronization Algorithms on Trees….Pages 334-348
Distance- k Information in Self-stabilizing Algorithms….Pages 349-356
Back Matter….Pages –