×

The Robertson-Seymour theorems: A survey of applications. (English) Zbl 0692.68030

Graphs and algorithms, Proc. Conf., Boulder/CO 1987, Contemp. Math. 89, 1-18 (1989).
Summary: [For the entire collection see Zbl 0678.00025.]
Applications of the Robertson-Seymour theorems to variety of problems in concrete computational complexity are surveyed. These results suggest a broad program of research in computational complexity based on partial orders of combinatorial objects defined by sequences of local operations. It is shown that the 2-induced connecting paths problem, relevant to the problem of order-testing in the strong minor order, is NP-complete. Approaches to practical algorithms achieving the Robertson-Seymour complexity bounds are described.

MSC:

68Q25 Analysis of algorithms and problem complexity
68-02 Research exposition (monographs, survey articles) pertaining to computer science

Citations:

Zbl 0678.00025