Graph Minors: Structure Theory and Algorithms
Robin B. Thomas · 1993
There have been significant developments in Graph Theory over the last decade that imply the existence of polynomial time algorithms for a large class of problems. These results, however, guarantee the existence of polynomial-time algorithms to solve various problems, but give no hint how to find one. Yet another drawback of these algorithms is that even though they are theoretically fast (O(n2) or O(n3)), the constant hidden in the 0 notation is so enormous that it makes the algorithms impractical. The purpose of this project is to (1) further develop this theory and obtain more theoretical results, (2) apply these results to the design of (at least theoretically) efficient algorithms, and (3) turn these theoretically efficient algorithms into practical ones.