Structural Information and Communication Complexity: 14th International Colloquium, SIROCCO 2007, Castiglioncello, Italy, June 5-8, 2007. Proceedings

Alessandro Panconesi (auth.), Giuseppe Prencipe, Shmuel Zaks (eds.)3540729186, 9783540729181

This book constitutes the refereed proceedings of the 14th International Colloquium on Structural Information and Communication Complexity, SIROCCO 2007, held in Castiglioncello, Italy in June 2007.

The 23 revised full papers presented together with 4 invited talks were carefully reviewed and selected from 66 submissions. The papers address issues such as distributed computing, high-speed networks, interconnection networks, mobile computing, optical computing, parallel computing, sensor networks, wireless networks, and autonomous robots. The papers are organized in topical sections on graph exploration, fault tolerance, distributed algorithms and data structures, location problems, wireless networks, fault tolerance, as well as parallel computing and selfish routing.

---

Table of contents :
Front Matter….Pages –
Fast Distributed Algorithms Via Primal-Dual (Extended Abstract)….Pages 1-6
Time Optimal Gathering in Sensor Networks….Pages 7-10
Treewidth: Structure and Algorithms….Pages 11-25
Fast Periodic Graph Exploration with Constant Memory….Pages 26-40
Why Robots Need Maps….Pages 41-50
Graph Searching with Advice….Pages 51-65
From Renaming to Set Agreement….Pages 66-80
A Self-stabilizing Algorithm for the Median Problem in Partial Rectangular Grids and Their Relatives….Pages 81-95
A New Self-stabilizing Maximal Matching Algorithm….Pages 96-108
Labeling Schemes with Queries….Pages 109-123
A Simple Optimistic Skiplist Algorithm….Pages 124-138
Data Aggregation in Sensor Networks: Balancing Communication and Delay Costs….Pages 139-150
Optimal Moves for Gossiping Among Mobile Agents….Pages 151-165
Swing Words to Make Circle Formation Quiescent….Pages 166-179
Distributed Algorithms for Partitioning a Swarm of Autonomous Mobile Robots….Pages 180-194
Local Edge Colouring of Yao-Like Subgraphs of Unit Disk Graphs….Pages 195-207
Proxy Assignments for Filling Gaps in Wireless Ad-Hoc Lattice Computers….Pages 208-221
Location Oblivious Distributed Unit Disk Graph Coloring….Pages 222-233
Edge Fault-Diameter of Cartesian Product of Graphs….Pages 234-245
Rapid Almost-Complete Broadcasting in Faulty Networks….Pages 246-260
Design of Minimal Fault Tolerant On-Board Networks: Practical Constructions….Pages 261-273
Dynamic Compass Models and Gathering Algorithms for Autonomous Mobile Robots….Pages 274-288
Fault-Tolerant Simulation of Message-Passing Algorithms by Mobile Agents….Pages 289-303
Optimal Conclusive Sets for Comparator Networks….Pages 304-317
Selfish Routing with Oblivious Users….Pages 318-327
Upper Bounds and Algorithms for Parallel Knock-Out Numbers….Pages 328-340
Back Matter….Pages –