Graph Algorithms in Networks

Overall rating: 4.33 Materials: 5.00 more …

In this webinar, we will examine mathematically how to understand different networking problems and concepts through the lens of graph algorithms, or computational graph theory. Graph problems can be broken into different types of problems based on the graph properties we seek. Examples and problems will be provided for users to try these concepts out for himself, as well as additional resources regarding implementation and data types for storing graph information.

The webinar will cover these topics:

• Tree, Path, and Center Problems;
• Flow and Connectivity Problems.

Each topic will be presented in a separate live session.

Contents

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.

The Author

Happy Campers