Polynomial-time self-reducibility: theoretical motivations and practical resultsFootnote^∗

References

• Abrahamson K. Fellows M. R. Langston M. A. Moret B. Constructive Complexity Washington State University 1988 Computer Science Technical Report CS-88-191
   Google Scholar
• Bryant , R. L. , Fellows , M. R. , Kinnersley , N. G. and Langston , M. A. 1987 . Proc. 25th Allerton Conf. on Communication, Control, and Computing . On finding obstruction sets and polynomial-time algorithms for gate matrix layout . 1987 . pp. 397 – 398 .
   Google Scholar
• Booth , K. S. and Lueker , G. S. 1976 . Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms . J. of Computer and System Sciences , 13 : 335 – 379 .
   Web of Science ®Google Scholar
• Conway , J. and Gordon , C. 1983 . Knots and links in spatial graphs . J. Graph Th. , 7 : 445 – 453 .
   Web of Science ®Google Scholar
• Deo , N. , Krishnamoorthy , M. S. and Langston , M. A. 1987 . Exact and appproximate solutions for the gate matrix layout problem . IEEE Trans. on Computer-Aided Design , 6 : 79 – 84 .
   Google Scholar
• Fellows , M. R. and Langston , M. A. 1987 . Nonconstructive advances in polynomial-time complexity . Info. Proc. Letters , 26 : 157 – 162 .
   Google Scholar
• Fellows , M. R. and Langston , M. A. 1988 . Nonconstructive tools for proving polynomial-time decidability . J. of the ACM , 35 : 727 – 739 .
   Google Scholar
• Fellows , M. R. and Langston , M. A. 1988 . Proc. 5th MIT Conf. on Advanced Research in VLSI . Layout permutation problems and well-partially-ordered sets . 1988 . pp. 315 – 327 .
   Google Scholar
• Fellows , M. R. and Langston , M. A. 1988 . Proc. 3rd Aegean Workshop on Computing . Fast self-reduction algorithms for combinatorial problems of VLSI design . 1988 . pp. 278 – 287 .
   Google Scholar
• Fellows , M. R. and Langston , M. A. 1989 . Proc. 21st ACM Symp. on Theory of Computing . On search, decision and the efficiency of polynomial-time algorithms . 1989 . pp. 501 – 512 .
   Google Scholar
• Friedman , H. , Robertson , N. and Seymour , P. D. “ The meta mathematics of the graph minor theorem ” . In Applications of Logic to Combinatorics , Providence, RI : American Math. Soc. . to appear
   Google Scholar
• Gilbert , J. R. , Hutchinson , J. P. and Tarjan , R. E. 1984 . A separator theorem for graphs of bounded genus . J. of Algorithms , 5 : 391 – 407 .
   Google Scholar
• Garey , M. R. and Johnson , D. S. 1979 . Computers and Intractability: A Guide to the Theory of NP-Completeness , San Francisco, CA : Freeman .
   Google Scholar
• Golumbic , M. C. 1980 . Algorithmic Graph Theory and Perfect Graphs , New York, NY : Academic Press .
   Google Scholar
• Hutchinson , J. P. and Miller , G. L. 1987 . On deleting vertices to make a graph of positive genus planar . Prospectives in Computing , 15 : 81 – 98 .
   Google Scholar
• Hashimoto , A. and Stevens , J. 1971 . Proc. 8th Design Automation Workshop . Wire routing by optimizing channel assignment within large apertures . 1971 . pp. 155 – 169 .
   Google Scholar
• Jaco W. private communication
   Google Scholar
• Johnson , D. S. 1987 . The many faces of polynomial time, in The NP-Completeness Column: An Ongoing Guide . J. Algorithms , 8 : 285 – 303 .
   Google Scholar
• Karp , R. M. and Lipton , R. J. 1980 . Proc. 12th ACM Symp. on Theory of Computing . Some connections between nonuniform and uniform complexity classes . 1980 . pp. 302 – 309 .
   Google Scholar
• Kuratowski , C. 1930 . Sur le probleme des curbes gauches en topologie . Fund. Math. , 15 : 271 – 283 .
   Google Scholar
• Karp , R. M. , Upfal , E. and Widgerson , A. 1985 . Proc. 17th ACM Symp. on Theory of Computing . Are search and decision problems computationally equivalent . 1985 . pp. 464 – 475 .
   Google Scholar
• Makedon F. S. Sudborough I. H. On minimizing width in linear layouts to appear
   Google Scholar
• Monien , B. 1985 . How to find long paths efficiently . Annals of Disc. Math. , 25 : 239 – 254 .
   Google Scholar
• Meyer A. Paterson M. With what frequency are apparently intractable problems difficult 1979 Technical Report, MIT
   Google Scholar
• Monien , B. and Sudburough , I. H. 1986 . Min cut is NP-complete for edge weighted trees . Lecture Notes in Computer Science , 226 : 265 – 274 .
   Google Scholar
• Ohtsuki , T. , Mori , H. , Kuh , E. S. , Kashiwabara , T. and Fujisawa , T. 1979 . One dimensional logic gate assignment and interval graphs . IEEE Trans. on Circuits and Systems , 26 : 675 – 684 .
   Google Scholar
• Robertson , N. and Seymour , P. D. 1985 . Disjoint paths—a survey . SIAM J. Alg. Disc. Meth. , 6 : 300 – 305 .
   Google Scholar
• Robertson , N. and Seymour , P. D. 1985 . “ Graph minors—a survey ” . In Surveys in Combinatorics , Edited by: Anderson , I. Cambridge University Press .
   Google Scholar
• Robertson , N. and Seymour , P. D. “ Graph Minors XIII ” . In The Disjoint Paths Problem to appear
   Google Scholar
• Robertson , N. and Seymour , P. D. “ Graph Minors XVI ” . In Wagner's Conjecture to appear
   Google Scholar
• Schnorr , C. P. 1976 . Optimal algorithms for self-reducible problems . Proc. ICALP , : 322 – 337 .
   Google Scholar
• Wagner , K. 1937 . Uber einer eigenschaft der ebener complexe . Math. Ann. , 14 : 570 – 590 .
   Google Scholar
• Yannakakis , M. 1985 . A polynomial algorithm for the min cut linear arrangement of trees . J. of the ACM , 32 : 950 – 959 .
   Web of Science ®Google Scholar