Graph Algorithms in Networks

Tree, Path, and Center Problems

The first session will focus on problems that can be expressed as finding trees (mostly spanning) and arborescences, paths, and locating different types of centers of a graph or network. The goals of this session are to understand how to translate a networking problem or request into more mathematical language, and to gain exposure to some of the algorithms used to solve these mathematical problems.

Some examples of questions and facts we’ll encounter:

• We can express the problem of informing every other node on a network of a new node’s presence in terms of finding a spanning arborescence of the network rooted at our new node, using the maximum branching algorithm.
• We’ll learn how one algorithm for finding spanning trees can be modified to find the minimum or maximum spanning tree when we weight each arc of a graph.
• We’ll really dig into how Dijkstra’s algorithm works, and some conditions under which it cannot. Then we’ll examine how to deal with cases Dijkstra’s algorithm cannot handle.
• We’ll look at more efficient ways to find the shortest paths between every pair of vertices in a network than repeated Dijkstra applications.
• We’ll examine the problem of finding the k shortest paths, when we’d like to know alternative paths, ranked in order of length.
• We’ll see how bottleneck problems can be reframed as path problems.
• We’ll examine general location problems, discussing different ways to measure distances and define centers. We’ll give examples of translating practical center problems to the correct type of center desired, and give algorithms and methods for finding such centers.
• We’ll introduce extensions to these types of problems, such as multi-location problems.
• Time permitting, we’ll hint at the unifying way to think of path algorithms in general in terms of matrix algebra and linear programming.

Flow and Connectivity Problems

In this second session on graph algorithms, we’ll examine graph connectivity and flow algorithms with applications to networks. We’ll look at methods to determine different types of connectivity in a graph, including finding the cut sets or bridges (weak points) of a network. We’ll spend the majority of the time discussing commodity flow algorithms and their applications to routing and load balancing. We’ll discuss the feasibility and existence of solutions as well.

Some examples of topics we’ll encounter:

• Maximum flow algorithm, finding the maximum flow units (packets, etc) from a source to a destination in a graph with arcs of given capacity so that no capacity or bandwidth is violated.
• Modification of the maximum flow algorithm to account for multiple sources and destinations.
• Minimum cost flow algorithm, and why this result may not match the maximum flow algorithm result.
• What dynamic flows are, and how this allows us to factor in a time component for flow through a graph or network.
• What happens when we allow flow units to change as they traverse an arc (either via gains or losses).
• The multicommodity flow problem and its difficulties.
• Finding cut sets of a graph, and their importance to applications.
• The max flow, min-cut theorem and the connection between connectivity and flow through a network.