Chapter 8 Algorithmic implications of the graph minor theorem

摘要: Publisher Summary This chapter describes some of the algorithmic ramifications graph minor theorem and its consequences. Significantly, many tools used in proof can be applied to a very broad class problems. For example, Robertson Seymour have obtained relatively simple polynomial-time algorithm for disjoint paths problem, task that had eluded researchers years. Other applications include combinatorial problems from several domains, including network routing, utilization design. Indeed, it is critical measure value Graph Minor Theorem so are already known it. Three types key notions employed minors, obstructions well-quasiorders. Kuratowski's may regarded as characterization planarity by means excluded graphs, henceforth termed obstructions. Characterizations this nature abound mathematics optimization. Some familiar examples max-flow min-cut theorem, Seymour's description clutters with property Farkas' lemma.