摘要: Abstract The history of graph algorithms so far exhibits a process evolution. In the early days (say up to 1960 or so) it was sufficient, given problem, find some algorithm that solved problem somehow. Later, consideration complexity, in time and space, started become paramount importance, concepts like NP-completeness focused attention on questions how efficient an might possibly be. This trend can be expected continue. It hints at growing level abstraction study algorithms. Theorems such as those Robertson Seymour, which, for example, demonstrate existence polynomial certain problems without exhibiting actual are signposts one direction which theory is going.
sci-hub.se 参考文章(21)
Andreas Blass, Frank Harary, Properties of almost all graphs and complexes Journal of Graph Theory. ,vol. 3, pp. 225- 240 ,(1979) , 10.1002/JGT.3190030305
Neil Robertson, P.D Seymour, Graph minors. VI. Disjoint paths across a disc Journal of Combinatorial Theory, Series B. ,vol. 41, pp. 115- 138 ,(1986) , 10.1016/0095-8956(86)90031-6
Michael R. Fellows, Michael A. Langston, Nonconstructive tools for proving polynomial-time decidability Journal of the ACM. ,vol. 35, pp. 727- 739 ,(1988) , 10.1145/44483.44491
Geoffrey Exoo, Frank Harary, The smallest graphs with certain adjacency properties Discrete Mathematics. ,vol. 29, pp. 25- 32 ,(1980) , 10.1016/0012-365X(90)90283-N
Neil Robertson, P. D. Seymour, Disjoint Paths—A Survey Siam Journal on Algebraic and Discrete Methods. ,vol. 6, pp. 300- 305 ,(1985) , 10.1137/0606030
Michael R. Fellows, Michael A. Langston, Nonconstructive advances in polynomial-time complexity Information Processing Letters. ,vol. 26, pp. 155- 162 ,(1987) , 10.1016/0020-0190(87)90054-8
Neil Robertson, P.D Seymour, Graph minors. III. Planar tree-width Journal of Combinatorial Theory, Series B. ,vol. 36, pp. 49- 64 ,(1984) , 10.1016/0095-8956(84)90013-3
Neil Robertson, P.D Seymour, Graph minors. VII. Disjoint paths on a surface Journal of Combinatorial Theory, Series B. ,vol. 45, pp. 212- 254 ,(1988) , 10.1016/0095-8956(88)90070-6
Neil Robertson, P.D Seymour, Graph minors. II: Algorithmic aspects of tree-width Journal of Algorithms. ,vol. 7, pp. 309- 322 ,(1986) , 10.1016/0196-6774(86)90023-4
Neil Robertson, P.D. Seymour, Graph minors. I. Excluding a forest Journal of Combinatorial Theory, Series B. ,vol. 35, pp. 39- 61 ,(1983) , 10.1016/0095-8956(83)90079-5