Combinatorial and Algorithmic Aspects of Networking: First Workshop on Combinatorial and Algorithmic Aspects of Networking, CAAN 2004, Banff, Alberta, Canada, August 5-7, 2004, Revised Selected Papers

M. Enachescu, A. Goel, R. Govindan, R. Motwani (auth.), Alejandro López-Ortiz, Angèle M. Hamel (eds.)3540278737, 9783540278733

This book constitutes the refereed proceedings of the first workshop on Combinatorial and Algorithmic Aspects of Networking, held in Banff, Alberta, Canada in August 2004.

The 12 revised full papers together with two invited papers presented were carefully reviewed and selected for inclusion in the book. The topics covered range from the web graph to game theory to string matching, all in the context of large-scale networks. This volume contains also 5 survey articles to round out the presentation and give a comprehensive introduction to the topic.

---

Table of contents :
Front Matter….Pages –
Aggregating Correlated Data in Sensor Networks….Pages 1-2
The Efficiency of Optimal Taxes….Pages 3-12
Congestion Games, Load Balancing, and Price of Anarchy….Pages 13-27
Bandwidth Allocation in Networks: A Single Dual Update Subroutine for Multiple Objectives….Pages 28-41
Limits and Power Laws of Models for the Web Graph and Other Networked Information Spaces….Pages 42-48
Cuts and Disjoint Paths in the Valley-Free Path Model of Internet BGP Routing….Pages 49-62
A Distributed Algorithm to Find Hamiltonian Cycles in $mathcal{G}(n, p)$ Random Graphs….Pages 63-74
String Matching on the Internet….Pages 75-89
k -Robust Single-Message Transmission….Pages 90-101
Stable Local Scheduling Algorithms With Low Complexity and Without Speedup for a Network of Input-Buffered Switches….Pages 102-113
The External Network Problem with Edge- or Arc-Connectivity Requirements….Pages 114-126
Bipartite Graphs as Models of Complex Networks….Pages 127-139
Traceroute-Like Exploration of Unknown Networks: A Statistical Analysis….Pages 140-153
Invited Talk: The Many Wonders of the Web Graph….Pages 154-154
Algorithmic Foundations of the Internet:Foreword….Pages 155-158
A Survey of Models of the Web Graph….Pages 159-172
You Can Get There from Here: Routing in the Internet….Pages 173-182
Search Engines and Web Information Retrieval….Pages 183-191
Algorithmic Foundations of the Internet: Roundup….Pages 192-204
Back Matter….Pages –