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.