ABSTRACT
This chapter discusses some useful graph-theoretic algorithms. It explores special path computation algorithms. The chapter provides basics of algebraic path techniques and related applications. It describes some problems related to the design of communication networks. The chapter analyzes graph-theoretic communication network model, linear network coding scheme, and its properties. The classical shortest path routing algorithms due to Bellman-Ford, Dijkstra, and Floyd-Warshall address the problem of minimizing a single metric associated with the arcs in the graph. The algorithm to determine the constrained path is essentially iterative. The disjoint path algorithm is developed in terms of a minimum cost flow problem in a capacitated network. The computational complexity of this algorithm depends upon the number of nodes in the tree. The proof of the correctness of this algorithm is left as an exercise to the reader. The matroid-theory based algorithm to compute network reliability is both efficient and elegant.
