Combinatorial and Algorithmic Aspects of Networking: Third Workshop, CAAN 2006 Chester, UK, July 2, 2006 Revised Papers

by Erlebach, Thomas

• ISBN13: 9783540488224
• ISBN10: 3540488227
• Format: Paperback
• Copyright: 2007-01-03
• Publisher: Textstream

Summary

This book constitutes the thoroughly refereed post-proceedings of the Third Workshop on Combinatorial and Algorithmic Aspects of Networking, held in Chester, UK in July 2006, co-located with the 13th Colloquium on Structural Information and Communication Complexity, SIROCCO 2006. The 10 revised full papers together with 1 invited lecture presented were carefully reviewed and selected from a total of 22 submissions. The topics covered range from the Web graph to game theory to string matching, all in the context of large-scale networks.

Table of Contents

Recent advances on approximation algorithms for minimum energy-range assignment problems in ad-hoc wireless networks	p. 1
The price of anarchy in selfish multicast routing	p. 5
Designing a truthful mechanism for a spanning arborescence bicriteria problem	p. 19
On the topologies of local minimum spanning trees	p. 31
Distributed routing in tree networks with few landmarks	p. 45
Scheduling of a smart antenna : capacitated coloring of unit circular-arc graphs	p. 58
On minimizing the number of ADMs - tight bounds for an algorithm without preprocessing	p. 72
Tolerance based contract-or-patch heuristic for the asymmetric TSP	p. 86
Acyclic type-of-relationship problems on the Internet	p. 98
Minimum-energy broadcasting in wireless networks in the d-dimensional euclidean space (the [alpha] [actual symbol not reproducible] d case)	p. 112
Optimal gossiping with unit size messages in known topology radio networks	p. 125
Table of Contents provided by Blackwell. All Rights Reserved.