Distributed Graph Algorithms for Computer Networks

  • 5h 34m
  • K. Erciyes
  • Springer
  • 2013

This book presents a comprehensive review of key distributed graph algorithms for computer network applications, with a particular emphasis on practical implementation. Topics and features: introduces a range of fundamental graph algorithms, covering spanning trees, graph traversal algorithms, routing algorithms, and self-stabilization; reviews graph-theoretical distributed approximation algorithms with applications in ad hoc wireless networks; describes in detail the implementation of each algorithm, with extensive use of supporting examples, and discusses their concrete network applications; examines key graph-theoretical algorithm concepts, such as dominating sets, and parameters for mobility and energy levels of nodes in wireless ad hoc networks, and provides a contemporary survey of each topic; presents a simple simulator, developed to run distributed algorithms; provides practical exercises at the end of each chapter.

In this Book

  • Introduction
  • Graphs
  • The Computational Model
  • Spanning Tree Construction
  • Graph Traversals
  • Minimum Spanning Trees
  • Routing
  • Self-Stabilization
  • Vertex Coloring
  • Maximal Independent Sets
  • Dominating Sets
  • Matching
  • Vertex Cover
  • Introduction
  • Topology Control
  • Ad Hoc Routing
  • Sensor Network Applications
  • ASSIST: A Simulator to Develop Distributed Algorithms