Graph and network algorithms

Abstract

Graphs provide a powerful tool to model objects and relationships among objects. The study of graphs dates back to Euler 's days in the 18th century, when he defined the Konigsberg bridge problem, and since then has been pursued by many researchers. Specifically, graphs can be used to model problems in many areas such as transportation, scheduling, networks, robotics, VLSI, compilers, mathematical biology, and software engineering. Many optimization problems from these and other diverse areas can be phrased in graph-theoretic terms, leading to algorithmic questions about graphs. Graphs. Graphs are defined by a set of vertices and a set of edges, where each edge connects two of its vertices. Graphs are further classified into directed and undirected graphs, depending on whether the edges are directed. An important subclass of directed graphs that arises in many applications, such as precedence-constrained scheduling problems, is directed acyclic graphs (DAG). Interesting