Structural Information and Communication Complexity: 20th International Colloquium, SIROCCO 2013, Ischia, Italy, July 1-3, 2013, Revised Selected Papers

by Thomas Moscibroda (Editor), Adele a Rescigno (Editor)

Distributed Community Detection in Dynamic Graphs.- Exploration of the T -Interval-Connected Dynamic The Case of the Ring.- A Characterization of Dynamic Networks Where Consensus Is Solvable.- Self-adjusting Grid Networks to Minimize Expected Path Length.- On Advice Complexity of the k-server Problem under Sparse Metrics.- Connected Surveillance Game.- Non-Additive Two-Option Ski Rental.- Competitive FIB Aggregation for Independent Online Ski Rental on the Trie.- A Nonmonotone Analysis with the Primal-Dual Online Routing of Virtual Circuits with Unknown Durations.- Self-organizing Flows in Social Networks.- Performance/Security Tradeoffs for Content-Based Routing Supported by Bloom Filters.- Influence Diffusion in Social Networks under Time Window Constraints.- Analysis of Fully Distributed Splitting and Naming Probabilistic Procedures and Applications.- A Deterministic Worst-Case Message Complexity Optimal Solution for Resource Discovery.- Maintaining Balanced Trees for Structured Distributed Streaming Systems.- Rendezvous of Two Robots with Constant Memory.- Pattern Formation by Mobile Robots with Limited Visibility.- Optimal Gathering of Oblivious Robots in Anonymous Graphs.- Probabilistic Connectivity Threshold for Directional Antenna Widths.- Broadcasting in Ad Hoc Multiple Access Channels.- Profit Maximization in Flex-Grid All-Optical Networks.- Measuring the Impact of Adversarial Errors on Packet Scheduling Strategies.- Optimal Buffer Management for 2-Frame Throughput Maximization.- Dynamically Maintaining Shortest Path Trees under Batches of Updates.- Simultaneous Consensus vs Set A Message-Passing-Sensitive Hierarchy of Agreement Problems.- Steiner Problems with Limited Number of Branching Nodes.- Exact and Approximate Algorithms for Movement Problems on (Special Classes of) Graphs.- Maximum Distance Separable Codes Based on Circulant Cauchy Matrices.

370 pages, Paperback

First published November 21, 2013