×

On search, decision, and the efficiency of polynomial-time algorithms. (English) Zbl 0938.68599


MSC:

68P10 Searching and sorting
68W05 Nonnumerical algorithms
68Q25 Analysis of algorithms and problem complexity
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] S. Cook and A. Gupta, private communication.
[2] 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)
[3] Fellows, M. R.; Langston, M. A.: Nonconstructive advances in polynomial-time complexity. Inform. proc. Lett. 26, 157-162 (1987) · Zbl 0637.68053
[4] Fellows, M. R.; Langston, M. A.: Nonconstructive tools for proving polynomial-time decidability. J. assoc. Comput. Mach 35, 727-739 (1988) · Zbl 0652.68049
[5] Fellows, M. R.; Langston, M. A.: On well-partional-order theory and its application to combinatorial problems of VLSI design. SIAM J. Discrete math. 5, 117-126 (1992) · Zbl 0739.68042
[6] Friedman, H.; Robertson, N.; Seymour, P. D.: The metamathematics of the graph minor theorem. Contemporary math. 65, 229-261 (1987) · Zbl 0635.03060
[7] Garey, M. R.; Johnson, D. S.: Computers and intractability. (1979) · Zbl 0411.68039
[8] Haken, W.: Theory der normalflächen. Acta math. 105, 245-375 (1961) · Zbl 0100.19402
[9] Levin, L. A.: Universal enumeration problems. Problemy peredachi informatsii 2, 115-116 (1972) · Zbl 0313.02026
[10] M. A. Langston and S. Ramachandramurthi, Dense layouts for series-parallel circuits, in ”Proceedings, 1991 Great Lake Symposium on VLSI”, pp. 14–17.
[11] Miller, G. L.: Rieman’s hypothesis and tests for primalty. J. comput. System sci. 13, 300-317 (1976) · Zbl 0349.68025
[12] B. Reed, Finding approximate separators and computing with tree width quickly, in ”Proceedings, 1992 Symposium on Theory of Computing,” pp. 221–228.
[13] Robertson, N.; Seymour, P. D.: Graph minors. IV. tree-width and well-quasi-ordering. J. combin. Theory ser. B 48, 227-254 (1990) · Zbl 0719.05032
[14] Robertson, N.; Seymour, P. D.: Graph minors. V. excluding a planar graph. J. combin. Theory ser. B 41, 92-114 (1986) · Zbl 0598.05055
[15] N. Robertson and P. D. Seymour, Graph minors. XIII. The disjoint paths problem, to appear. · Zbl 0823.05038
[16] N. Robertson and P. D. Seymour, Graph minors. XVI. Wagners conjecture, to appear.
[17] C. P. Schnorr, Optimal algorithms for self-reducible problems in ”Proceedings, 1976 International Conference on Automata, Programming and Languages,” pp. 322–337.
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.