This book constitutes the refereed proceedings of the 17th International Colloquium on Structural Information and Communication Complexity, SIROCCO 2010, held in Sirince, Turkey, in June 2010. The 19 revised full papers presented were carefully reviewed and selected from 37 submissions. The volume also contains the abstract of one invited talk. The papers are organized in topical section on game theory, network algorithms, motion planning, asynchrony, network algorithms, motion planning, topology algorithms, and graph algorithms.
Author(s): Eyal Kushilevitz (auth.), Boaz Patt-Shamir, Tınaz Ekim (eds.)
Series: Lecture Notes in Computer Science 6058 : Theoretical Computer Science and General Issues
Edition: 1
Publisher: Springer-Verlag Berlin Heidelberg
Year: 2010
Language: English
Pages: 273
Tags: Algorithm Analysis and Problem Complexity; Computer Communication Networks; Discrete Mathematics in Computer Science; Data Structures; Algorithms
Front Matter....Pages -
Communication Complexity: From Two-Party to Multiparty....Pages 1-1
On the Impact of Local Taxes in a Set Cover Game....Pages 2-13
Towards Network Games with Social Preferences....Pages 14-28
Distributed Weighted Stable Marriage Problem....Pages 29-40
Traffic Grooming in Star Networks via Matching Techniques....Pages 41-56
Event Extent Estimation....Pages 57-71
Asynchronous Deterministic Rendezvous in Bounded Terrains....Pages 72-85
Space-Optimal Rendezvous of Mobile Agents in Asynchronous Trees....Pages 86-100
Mobile Robots Gathering Algorithm with Local Weak Multiplicity in Rings....Pages 101-113
Average Long-Lived Memoryless Consensus: The Three-Value Case....Pages 114-126
Algorithms for Extracting Timeliness Graphs....Pages 127-141
Distributed Tree Comparison with Nodes of Limited Memory....Pages 142-156
Periodic Data Retrieval Problem in Rings Containing a Malicious Host....Pages 157-167
A Continuous, Local Strategy for Constructing a Short Chain of Mobile Robots....Pages 168-182
Optimal Deterministic Ring Exploration with Oblivious Asynchronous Robots....Pages 183-196
Maximum Interference of Random Sensors on a Line....Pages 197-210
Multipath Spanners....Pages 211-223
Strong Orientations of Planar Graphs with Bounded Stretch Factor....Pages 224-236
A Linear Time Algorithm for the Minimum Spanning Caterpillar Problem for Bounded Treewidth Graphs....Pages 237-246
Fast Algorithms for min independent dominating set ....Pages 247-261
Back Matter....Pages -
