×

zbMATH — the first resource for mathematics

Improved self-reduction algorithms for graphs with bounded treewidth. (English) Zbl 0941.68652

MSC:
68R10 Graph theory (including graph drawing) in computer science
68Q25 Analysis of algorithms and problem complexity
05C35 Extremal problems in graph theory
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Arnborg, S.: Efficient algorithms for combinatorial problems on graphs with bounded decomposability – a survey. Bit 25, 2-23 (1985) · Zbl 0573.68018
[2] Arnborg, S.; Corneil, D. G.; Proskurowski, A.: Complexity of finding embeddings in a k-tree. SIAM J. Algebraic discrete methods 8, 277-284 (1987) · Zbl 0611.05022
[3] Arnborg, S.; Courcelle, B.; Proskurowski, A.; Seese, D.: An algebraic theory of graph reduction. J. ACM 40, 1134-1164 (1993) · Zbl 0795.68156
[4] Arnborg, S.; Lagergren, J.; Seese, D.: Easy problems for tree-decomposable graphs. J. algorithms 12, 308-340 (1991) · Zbl 0734.68073
[5] Arnborg, S.; Proskurowski, A.: Characterization and recognition of partial 3-trees. SIAM J. Algebraic discrete methods 7, 305-314 (1986) · Zbl 0597.05027
[6] Arnborg, S.; Proskurowski, A.: Linear time algorithms for NP-hard problems restricted to partial k-trees. Discrete appl. Math. 23, 11-24 (1989) · Zbl 0666.68067
[7] Bodlaender, H. L.: Dynamic programming algorithms on graphs with bounded tree-width. (1987)
[8] Bodlaender, H. L.: NC-algorithms for graphs with small treewidth. Proceedings workshop on graph-theoretic concepts in computer science WG’88 344, 1-10 (1988)
[9] Bodlaender, H. L.: Some classes of graphs with bounded treewidth. Bull. EATCS 36, 116-126 (1988) · Zbl 0684.68047
[10] Borie, R. B.; Parker, R. G.; Tovey, C. A.: Automatic generation of linear algorithms from predicate calculus descriptions of problems on recursive constructed graph families. Algorithmica 7, 555-581 (1992) · Zbl 0753.05062
[11] Brown, D. J.; Fellows, M. R.; Langston, M. A.: Nonconstructive polynomial-time decidability and self-reducibility. Internat. J. Comput. math. 31, 1-9 (1989) · Zbl 0825.68410
[12] Courcelle, B.: The monadic second-order logic of graphs III: Treewidth, forbidden minors and complexity issues. Informatique théorique 26, 257-286 (1992) · Zbl 0754.03006
[13] Courcelle, B.: The monadic second-order logic of graphs. I: recognizable sets of finite graphs. Inform. and comput. 85, 12-75 (1990) · Zbl 0722.03008
[14] Fellows, M. R.; Abrahamson, K.: Finite automata, bounded treewidth and well-quasiordering. Contemp. math. 147, 539-564 (1993) · Zbl 0791.05094
[15] Fellows, M. R.; Langston, M. A.: Nonconstructive advances in polynomial-time complexity. Inform. process. Lett. 26, 157-162 (1987) · Zbl 0637.68053
[16] Fellows, M. R.; Langston, M. A.: Fast self-reduction algorithms for combinatorial problems of VLSI design. Proceedings of the 3rd aegean workshop on computing 319, 278-287 (1988) · Zbl 0652.68048
[17] Fellows, M. R.; Langston, M. A.: On well-partial-order theory and its application to combinatorial problems of VLSI design. SIAM J. Discrete methods 5, 117-126 (1992) · Zbl 0739.68042
[18] Fellows, M. R.; Langston, M. A.: Nonconstructive tools for proving polynomial-time decidability. J. ACM 35, 727-739 (1988) · Zbl 0652.68049
[19] Fellows, M. R.; Langston, M. A.: An analogue of the myhill-nerode of the theorem and its use in computing finite-basis characterizations. Proceedings 29th annual symposium on foundations of computing science (FOCS), 520-525 (1989)
[20] Fellows, M. R.; Langston, M. A.: On search, decision and the efficiency of polynomial-time algorithms. Proceedings of the 21st annual ACM symposium on theory of computing (STOC), 501-512 (1989)
[21] Kirousis, L. M.; Papadimitriou, C. H.: Searching and pebbling. Theoret. comput. Sci. 47, 205-218 (1986) · Zbl 0616.68064
[22] Lagergren, J.: Efficient parallel algorithms for tree-decomposition and related problems. Proceedings 30th annual symposium on foundations of computing science (FOCS), 173-182 (1990)
[23] Lapaugh, A. S.: Recontamination does not help to search a graph. J. ACM 40, 224-245 (1993) · Zbl 0768.68048
[24] Lautemann, C.: Efficient algorithms on context-free graph languages. Proceedings of the 15th ICALP 317, 362-378 (1988) · Zbl 0649.68075
[25] Lengauer, T.: Black-white pebbles and graph separation. Acta inform. 16, 465-475 (1981) · Zbl 0454.68027
[26] Matousěk, J.; Thomas, R.: Algorithms finding tree-decompositions of graphs. J. algorithms 12, 1-22 (1991) · Zbl 0712.68077
[27] Megiddo, N.; Hakimi, S. L.; Garey, M. R.; Johnson, D. S.; Papadimitriou, C. H.: The complexity of searching of graph. J. ACM 35, 18-44 (1988) · Zbl 0637.68081
[28] Monien, B.; Sudborough, I. H.: MIN cut is NP-complete for edge weighted trees. Theoret. comput. Sci. 58, 209-229 (1988) · Zbl 0657.68034
[29] Robertson, N.; Seymour, P. D.: Graph minors IV: Tree-width and well-quasi-ordering. J. combin. Theory ser. B 48, 115-138 (1986) · Zbl 0598.05042
[30] N. Robertson and P.D. Seymour, Graph minors XVI: Wagner’s conjecture, to appear. · Zbl 1061.05088
[31] Robertson, N.; Seymour, P. D.: Graph minors III: Planar tree-width. J. combin. Theory ser. B 36, 49-64 (1984) · Zbl 0548.05025
[32] Robertson, N.; Seymour, P. D.: Graph minors II: Algorithmic aspects of tree-width. J. algorithms 7, 309-322 (1986) · Zbl 0611.05017
[33] Robertson, N.; Seymour, P. D.: Graph minors X: Obstructions to tree-decompositions. J. combin. Theory ser. B 52, 153-190 (1991) · Zbl 0764.05069
[34] Robertson, N.; Seymour, P. D.: Graph minors XIII: The disjoint paths problem. (1986) · Zbl 0823.05038
[35] Scheffler, P.: Linear-time algorithms for NP-complete problems restricted to partial k-trees. (1987) · Zbl 0629.68043
[36] Bodlaender, H. L.: A linear time algorithm for finding tree-decompositions of small treewidth. Proceedings 25th STOC, 226-234 (1993) · Zbl 1310.05194
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.