ABSTRACT
Finding disjoint paths in graphs is a problem that has attracted considerable attention from at least three perspectives: graph theory, VLSI design, and network routing/flow. The corresponding literature is extensive. In the current chapter, we focus mostly on results on offline approximation algorithms for problems on general graphs as influenced from the network flow perspective. Surveys examining the underlying graph theory, combinatorial problems in VLSI, and disjoint paths on special graph classes can be found in References 1–8. We sporadically mention some results on fixed-parameter tractability, but this is not an aspect this survey covers at any depth.
