{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T16:38:23Z","timestamp":1725467903492},"publisher-location":"Berlin\/Heidelberg","reference-count":41,"publisher":"Springer-Verlag","isbn-type":[{"type":"print","value":"0387968180"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/bfb0040395","type":"book-chapter","created":{"date-parts":[[2006,8,3]],"date-time":"2006-08-03T00:03:50Z","timestamp":1154563430000},"page":"278-287","source":"Crossref","is-referenced-by-count":6,"title":["Fast self-reduction algorithms for combinatorial problems of VLSI design"],"prefix":"10.1007","author":[{"given":"Michael R.","family":"Fellows","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Michael A.","family":"Langston","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"28_CR1","unstructured":"K. Abrahamson, M. R. Fellows, M. A. Langston and B. Moret, \u201cConstructive Complexity,\u201d to appear."},{"key":"28_CR2","unstructured":"S. Arnborg and A. Proskurowski, \u201cLinear Time Algorithms for NP-hard Problems on Graphs Embedded in k-trees,\u201d TRITA-NA-8404, The Royal Institute of Technology (1984)."},{"key":"28_CR3","unstructured":"S. R. Buss and M. R. Fellows, \u201cAchieving the Robertson-Seymour Bounds: k-Feedback and Related Vertex Sets,\u201d to appear."},{"key":"28_CR4","unstructured":"R. L. Bryant, M. R. Fellows, N. G. Kinnersley and M. A. Langston, \u201cOn Finding Obstruction Sets and Polynomial-Time Algorithms for Gate Matrix Layout,\u201d Proc. 25th Allerton Conf. on Communication, Control, and Computing (1987), 397\u2013398."},{"key":"28_CR5","unstructured":"D. J. Brown, M. R. Fellows and M. A. Langston, \u201cPolynomial-Time Self-Reducibility: Theoretical Motivations and Practical Results,\u201d Computer Science Technical Report CS-87-171, Washington State University, 1987."},{"key":"28_CR6","doi-asserted-by":"crossref","unstructured":"M. W. Bern, E. L. Lawler and A. L. Wong, \u201cWhy Certain Subgraph Computations Require Only Linear Time,\u201d Proc. 26th IEEE Symposium the Foundations of Computer Science (1985), 117\u2013125.","DOI":"10.1109\/SFCS.1985.66"},{"key":"28_CR7","unstructured":"H. L. Bodlaender, \u201cClasses of Graphs with Bounded Tree-Width,\u201d Technical Report RUU-CS-86-22, Department of Computer Science, University of Utrecht, 1986."},{"key":"28_CR8","volume-title":"Extremal Graph Theory","author":"B. Bollab\u00e1s","year":"1978","unstructured":"B. Bollab\u00e1s, Extremal Graph Theory, Academic Press, New York, 1978."},{"key":"28_CR9","unstructured":"M. Blum and S. Rudich, private communication."},{"key":"28_CR10","doi-asserted-by":"publisher","first-page":"79","DOI":"10.1109\/TCAD.1987.1270248","volume":"6","author":"N. Deo","year":"1987","unstructured":"N. Deo, M. S. Krishnamoorthy and M. A. Langston, \u201cExact and Approximate Solutions for the Gate Matrix Layout Problem,\u201d IEEE Trans. on Computer-Aided Design 6 (1987), 79\u201384.","journal-title":"IEEE Trans. on Computer-Aided Design"},{"key":"28_CR11","unstructured":"J. Ellis, I. H. Sudborough and J. Turner, \u201cGraph Separation and Search Number,\u201d to appear."},{"key":"28_CR12","doi-asserted-by":"crossref","unstructured":"M. R. Fellows, \u201cApplications of the Robertson-Seymour Theorems: A Survey,\u201d to appear.","DOI":"10.1090\/conm\/089\/1006472"},{"key":"28_CR13","doi-asserted-by":"publisher","first-page":"157","DOI":"10.1016\/0020-0190(87)90054-8","volume":"26","author":"M. R. Fellows","year":"1987","unstructured":"M. R. Fellows and M. A. Langston, \u201cNonconstructive Advances in Polynomial-Time Complexity,\u201d Info. Proc. Letters 26 (1987), 157\u2013162.","journal-title":"Info. Proc. Letters"},{"key":"28_CR14","unstructured":"\u2014, \u201cNonconstructive Tools for Proving Polynomial-Time Decidability,\u201d J. of the ACM, to appear."},{"key":"28_CR15","unstructured":"\u2014, \u201cLayout Permutation Problems and Well-Partially-Ordered Sets,\u201d Proc. 5th MIT Conf. on Advanced Research in VLSI (1988), to appear."},{"key":"28_CR16","unstructured":"H. Friedman, N. Robertson and P. D. Seymour, \u201cThe Metamathematics of the Graph Minor Theorem,\u201d in Applications of Logic to Combinatorics, American Math. Soc., Providence, RI, to appear."},{"key":"28_CR17","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"M. R. Garey","year":"1979","unstructured":"M. R. Garey and D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, Freeman, San Francisco, CA, 1979."},{"key":"28_CR18","doi-asserted-by":"publisher","first-page":"531","DOI":"10.1016\/0196-6774(84)90006-3","volume":"5","author":"E. M. Gurari","year":"1984","unstructured":"E. M. Gurari and I. H. Sudborough, \u201cImproved Dynamic Programming Algorithms for Bandwidth Minimization and the Min Cut Linear Arrangement Problem,\u201d J. of Algorithms 5 (1984), 531\u2013546.","journal-title":"J. of Algorithms"},{"key":"28_CR19","doi-asserted-by":"publisher","first-page":"285","DOI":"10.1016\/0196-6774(87)90043-5","volume":"8","author":"D. S. Johnson","year":"1987","unstructured":"D. S. Johnson, \u201cThe Many Faces of Polynomial Time,\u201d in The NP-Completeness Column: An Ongoing Guide, J. Algorithms 8 (1987), 285\u2013303.","journal-title":"J. Algorithms"},{"key":"28_CR20","unstructured":"T. Kashiwabara and T. Fujisawa, \u201cNP-completeness of the Problem of Finding a Minimum-Clique-Number Interval Graph Containing a Given Graph as a Subgraph,\u201d Proc. IEEE Symp. on Circuits and Systems (1979), 657\u2013660."},{"key":"28_CR21","volume-title":"The Art of Computer Programming, Vol. 3: Sorting and Searching","author":"D. E. Knuth","year":"1973","unstructured":"D. E. Knuth, The Art of Computer Programming, Vol. 3: Sorting and Searching, Addison-Wesley, Reading, MA, 1973."},{"key":"28_CR22","series-title":"Technical Report","volume-title":"Searching and Pebbling","author":"M. Kirousis","year":"1983","unstructured":"M. Kirousis and C. H. Papadimitriou, \u201cSearching and Pebbling,\u201d Technical Report, National Technical University, Athens, Greece, 1983."},{"key":"28_CR23","doi-asserted-by":"crossref","unstructured":"R. M. Karp, E. Upfal and A. Wigderson, \u201cAre Search and Decision Problems Computationally Equivalent,\u201d Proc. 17th ACM Symp. on Theory of Computing (1985), 464\u2013475.","DOI":"10.1145\/22145.22197"},{"key":"28_CR24","doi-asserted-by":"publisher","first-page":"465","DOI":"10.1007\/BF00264496","volume":"16","author":"T. Lengauer","year":"1981","unstructured":"T. Lengauer, \u201cBlack-White Pebbles and Graph Separation,\u201d Acta Informatica 16 (1981), 465\u2013475.","journal-title":"Acta Informatica"},{"key":"28_CR25","doi-asserted-by":"publisher","first-page":"145","DOI":"10.1016\/S0167-5060(08)70504-1","volume":"3","author":"W. Mader","year":"1978","unstructured":"W. Mader, \u201cA Reduction Method for Edge-Connectivity in Graphs,\u201d Annals of Disc. Math 3 (1978), 145\u2013164.","journal-title":"Annals of Disc. Math"},{"key":"28_CR26","unstructured":"F. S. Makedon and I. H. Sudborough, \u201cOn Minimizing Width in Linear Layouts,\u201d to appear."},{"key":"28_CR27","unstructured":"N. Megiddo, S. L. Hakimi, M. R. Garey, D. S. Johnson and C. H. Papadimitriou, \u201cOn the Complexity of Searching a Graph,\u201d IBM Research Report RJ 4987, 1986."},{"key":"28_CR28","unstructured":"Z. Miller and I. H. Sudborough, \u201cPolynomial Algorithms for Recognizing Small Cutwidth in Hypergraphs,\u201d to appear."},{"key":"28_CR29","doi-asserted-by":"publisher","first-page":"697","DOI":"10.1017\/S0305004100039062","volume":"61","author":"C. Nash-Williams","year":"1965","unstructured":"C. Nash-Williams, \u201cOn Well-Quasi-Ordering Infinite Trees,\u201d Proc. Cambridge Phil. Soc. 61 (1965), 697\u2013720.","journal-title":"Proc. Cambridge Phil. Soc."},{"key":"28_CR30","doi-asserted-by":"crossref","first-page":"150","DOI":"10.1007\/3-540-10291-4_12","volume":"100","author":"A. Rosenberg","year":"1981","unstructured":"A. Rosenberg, \u201cIssues in the Study of Graph Embeddings,\u201d Lecture Notes in Computer Science 100 (1981), 150\u2013176.","journal-title":"Lecture Notes in Computer Science"},{"key":"28_CR31","doi-asserted-by":"crossref","first-page":"300","DOI":"10.1137\/0606030","volume":"6","author":"N. Robertson","year":"1985","unstructured":"N. Robertson and P. D. Seymour, \u201cDisjoint Paths-a Survey,\u201d SIAM J. Alg. Disc. Meth. 6 (1985), 300\u2013305.","journal-title":"SIAM J. Alg. Disc. Meth."},{"key":"28_CR32","unstructured":"\u2014, \u201cGraph Minors\u2014a Survey,\u201d in Surveys in Combinatorics (I. Anderson, ed.), Cambridge Univ. Press, 1985."},{"key":"28_CR33","doi-asserted-by":"publisher","first-page":"39","DOI":"10.1016\/0095-8956(83)90079-5","volume":"35","author":"N. Robertson","year":"1983","unstructured":"\u2014, \u201cGraph Minors I. Excluding a Forest,\u201d J. Comb. Th. Ser. B 35 (1983), 39\u201361.","journal-title":"J. Comb. Th. Ser. B"},{"key":"28_CR34","unstructured":"\u2014, \u201cGraph Minors IV. Tree-Width and Well-Quasi-Ordering,\u201d to appear."},{"key":"28_CR35","unstructured":"\u2014, \u201cGraph Minors XIII. The Disjoint Paths Problem,\u201d to appear."},{"key":"28_CR36","unstructured":"\u2014, \u201cGraph Minors XVI. Wagner's Conjecture,\u201d to appear."},{"key":"28_CR37","unstructured":"D. Seese, \u201cTree-Partite Graphs and the Complexity of Algorithms,\u201d Preprint P-Math-08\/86, Karl-Weierstrass-Institut f\u00fcr Mathematik, Akademie der Wissenschaften der DDR, 1986."},{"key":"28_CR38","unstructured":"P. Scheffler and D. Seese, \u201cGraphs of Bounded Tree-Width and Linear-Time Algorithms for NP-Complete Problems,\u201d manuscript, 1986."},{"key":"28_CR39","doi-asserted-by":"publisher","first-page":"570","DOI":"10.1007\/BF01594196","volume":"14","author":"K. Wagner","year":"1937","unstructured":"K. Wagner, \u201cUber Einer Eigenshaft der Ebener Complexe,\u201d Math. Ann. 14 (1937), 570\u2013590.","journal-title":"Math. Ann."},{"key":"28_CR40","first-page":"43","volume":"50","author":"T. V. Wimer","year":"1985","unstructured":"T. V. Wimer, S. T. Hedetniemi and R. Laskar, \u201cA Methodology for Constructing Linear Graph Algorithms,\u201d Congressus Numerantium 50 (1985), 43\u201360.","journal-title":"Congressus Numerantium"},{"key":"28_CR41","unstructured":"T. V. Wimer, \u201cLinear Algorithms on k-Terminal Graphs,\u201d Ph.D. Dissertation, Clemson University, 1987."}],"container-title":["Lecture Notes in Computer Science","VLSI Algorithms and Architectures"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/www.springerlink.com\/index\/pdf\/10.1007\/BFb0040395","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,11,5]],"date-time":"2019-11-05T05:37:55Z","timestamp":1572932275000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BFb0040395"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["0387968180"],"references-count":41,"URL":"https:\/\/doi.org\/10.1007\/bfb0040395","relation":{},"subject":[]}}