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

David Peleg (auth.), Thomas Erlebach (eds.)3540488227, 9783540488224

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 :
Front Matter….Pages –
Recent Advances on Approximation Algorithms for Minimum Energy Range Assignment Problems in Ad-Hoc Wireless Networks….Pages 1-4
The Price of Anarchy in Selfish Multicast Routing….Pages 5-18
Designing a Truthful Mechanism for a Spanning Arborescence Bicriteria Problem….Pages 19-30
On the Topologies of Local Minimum Spanning Trees….Pages 31-44
Distributed Routing in Tree Networks with Few Landmarks….Pages 45-57
Scheduling of a Smart Antenna: Capacitated Coloring of Unit Circular-Arc Graphs….Pages 58-71
On Minimizing the Number of ADMs – Tight Bounds for an Algorithm Without Preprocessing….Pages 72-85
Tolerance Based Contract-or-Patch Heuristic for the Asymmetric TSP….Pages 86-97
Acyclic Type-of-Relationship Problems on the Internet….Pages 98-111
Minimum-Energy Broadcasting in Wireless Networks in the d -Dimensional Euclidean Space (The α ≤ d Case)….Pages 112-124
Optimal Gossiping with Unit Size Messages in Known Topology Radio Networks….Pages 125-134
Back Matter….Pages –