| |
This book constitutes the refereed proceedings of the 12th International Colloquium on Structural Information and Communication Complexity, SIROCCO 2005, held in Mont Saint-Michel, France in May 2005.
The 22 revised full papers presented were carefully reviewed and selected from 48 submissions. The papers address issues such as topics in distributed and parallel computing, information dissemination, communication complexity, interconnection networks, high speed networks, wireless networking, mobile computing, optical computing, and related areas
Table Of Contents:
On designing truthful mechanisms for online scheduling3On private computation in incomplete networks18Traffic grooming on the path34Range augmentation problems in static ad-hoc wireless networks49On the approximability of the L(h, k)-labelling problem on bipartite graphs65A tight bound for online coloring of disk graphs78Divide and conquer is almost optimal for the bounded-hop MST problem on random Euclidean instances89Distributed exploration of an unknown graph99Two absolute bounds for distributed bit complexity115Finding short right-hand-on-the-wall walks in graphs127Space lower bounds for graph exploration via reduced automata140Communications in unknown networks : preserving the secret of topology155An improved algorithm for adaptive condition-based consensus170Biangular circle formation by asynchronous mobile robots185Hardness and approximation results for black hole search in arbitrary graphs200On semi-perfect 1-factorizations216Free-riders in Steiner tree cost-sharing games231On the feasibility of gathering by autonomous mobile robots246Majority and unanimity in synchronous networks with ubiquitous dynamic faults262Minimizing the number of ADMs in SONET rings with maximum throughput277Optimal gossiping in square meshes in all-port mode and with short packets292Geometric routing without geometry307 ISBN - 9783540260523
|
| |
Pages : 323
|