zbMATH — the first resource for mathematics

Obstruction set isolation for the gate matrix layout problem. (English) Zbl 0941.68590

68Q25 Analysis of algorithms and problem complexity
68R10 Graph theory (including graph drawing) in computer science
Full Text: DOI
[1] Bondy, J.A.; Murty, U.S.R., Graph theory with applications, (1976), North-Holland New York · Zbl 1134.05001
[2] Bryant, R.L.; Fellows, M.R.; Kinnersley, N.G.; Langston, M.A., On finding obstruction sets and polynomial-time algorithms for gate matrix layout, Proceedings of the 25th allerton conference on communication, control, and computing, 397-398, (1987)
[3] Brown, D.J.; Fellows, M.R.; Langston, M.A., Polynomial-time self-reducibility: theoretical motivations and practical results, Internat. J. comput. math., 31, 1-9, (1989) · Zbl 0825.68410
[4] Deo, N.; Krishnamoorthy, M.S.; Langston, M.A., Exact and approximate solutions for the gate matrix layout problem, IEEE trans. computer-aided design, 6, 79-84, (1987)
[5] J.A. Ellis, I.H. Sudborough and J.S. Turner, The vertex separation and search number of a graph, Inform. and Comput., to appear. · Zbl 0942.68641
[6] Fellows, M.R.; Langston, M.A., Nonconstructive advances in polynomial-time complexity, Inform. process. lett., 26, 157-162, (1987) · Zbl 0637.68053
[7] Fellows, M.R.; Langston, M.A., Nonconstructive tools for providing polynomial-time decidability, J. ACM, 35, 727-739, (1988) · Zbl 0652.68049
[8] Fellows, M.R.; Langston, M.A., On well-partial-order theory and its application to combinatorial problems of VLSI design, SIAM J. discrete math., 5, 117-126, (1992) · Zbl 0739.68042
[9] Fellows, M.R.; Langston, M.A., Fast search algorithms for layout permutation problems, Internat. J. comput. aided VLSI design, 3, 325-342, (1991)
[10] Fellows, M.R.; Langston, M.A., On search, decision and the efficiency of polynomial-time algorithms, Proceedings of the 21st ACM symposium on the theory of computing, 501-512, (1989)
[11] Harary, F., Graph theory, (1969), Addison-Wesley Reading, MA · Zbl 0797.05064
[12] Kinnersley, N.G., Obstruction set isolation for layout permutation problems, Ph.D. thesis, (1989), Washington State University
[13] Kuratowski, C., Sur le probleme des curbes gauches en topologie, Fund. math., 15, 271-283, (1930) · JFM 56.1141.03
[14] Robertson, N.; Seymour, P.D., Graph minors I. excluding a forest, J. combin. theory ser. B, 35, 39-61, (1983) · Zbl 0521.05062
[15] Robertson, N.; Seymour, P.D., Graph minors V. excluding a planar graph, J. combin. theory ser. B, 41, 92-114, (1986) · Zbl 0598.05055
[16] N. Robertson and P.D. Seymour, Graph minors XIII. The disjoint paths problems, to appear. · Zbl 0823.05038
[17] N. Robertson and P.D. Seymour, Graph minors XVI. Wagner’s conjecture, to appear. · Zbl 1061.05088
[18] P.D. Seymour, private communication.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.