×

zbMATH — the first resource for mathematics

Polynomial-time self-reducibility: Theoretical motivations and practical results. (English) Zbl 0825.68410

MSC:
68Q25 Analysis of algorithms and problem complexity
68R10 Graph theory (including graph drawing) in computer science
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Abrahamson K., Constructive Complexity (1988)
[2] 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.
[3] Booth K. S., J. of Computer and System Sciences 13 pp 335– (1976) · Zbl 0367.68034 · doi:10.1016/S0022-0000(76)80045-1
[4] Conway J., J. Graph Th. 7 pp 445– (1983) · Zbl 0524.05028 · doi:10.1002/jgt.3190070410
[5] Deo N., IEEE Trans. on Computer-Aided Design 6 pp 79– (1987) · Zbl 05447855 · doi:10.1109/TCAD.1987.1270248
[6] Fellows M. R., Info. Proc. Letters 26 pp 157– (1987) · Zbl 0637.68053 · doi:10.1016/0020-0190(87)90054-8
[7] Fellows M. R., J. of the ACM 35 pp 727– (1988) · Zbl 0652.68049 · doi:10.1145/44483.44491
[8] 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.
[9] 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. · Zbl 0652.68048
[10] 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.
[11] Friedman H., Applications of Logic to Combinatorics
[12] Gilbert J. R., J. of Algorithms 5 pp 391– (1984) · Zbl 0556.05022 · doi:10.1016/0196-6774(84)90019-1
[13] Garey M. R., Computers and Intractability: A Guide to the Theory of NP-Completeness (1979) · Zbl 0411.68039
[14] Golumbic M. C., Algorithmic Graph Theory and Perfect Graphs (1980) · Zbl 0541.05054
[15] Hutchinson J. P., Prospectives in Computing 15 pp 81– (1987)
[16] Hashimoto, A. and Stevens, J. 1971.Proc. 8th Design Automation Workshop. Wire routing by optimizing channel assignment within large apertures. 1971. pp.155–169.
[17] Jaco W., private communication
[18] Johnson D. S., J. Algorithms 8 pp 285– (1987) · Zbl 0626.68039 · doi:10.1016/0196-6774(87)90043-5
[19] 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.
[20] Kuratowski C., Fund. Math. 15 pp 271– (1930)
[21] 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.
[22] Makedon F. S., On minimizing width in linear layouts · Zbl 0514.94025
[23] Monien B., Annals of Disc. Math. 25 pp 239– (1985)
[24] Meyer A., With what frequency are apparently intractable problems difficult (1979)
[25] Monien B., Lecture Notes in Computer Science 226 pp 265– (1986) · doi:10.1007/3-540-16761-7_76
[26] Ohtsuki T., IEEE Trans. on Circuits and Systems 26 pp 675– (1979) · Zbl 0414.94052 · doi:10.1109/TCS.1979.1084695
[27] Robertson N., SIAM J. Alg. Disc. Meth. 6 pp 300– (1985) · Zbl 0565.05045 · doi:10.1137/0606030
[28] Robertson N., Surveys in Combinatorics (1985)
[29] Robertson N., The Disjoint Paths Problem · Zbl 0823.05038
[30] Robertson N., Wagner’s Conjecture · Zbl 1061.05088
[31] Schnorr C. P., Proc. ICALP pp 322– (1976)
[32] Wagner K., Math. Ann. 14 pp 570– (1937) · Zbl 0017.19005 · doi:10.1007/BF01594196
[33] Yannakakis M., J. of the ACM 32 pp 950– (1985) · Zbl 0633.68063 · doi:10.1145/4221.4228
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.