×

zbMATH — the first resource for mathematics

Directed tree-width. (English) Zbl 1027.05045
Summary: We generalize the concept of tree-width to directed graphs and prove that every directed graph with no “haven” of large order has small tree-width. Conversely, a digraph with a large haven has large tree-width. We also show that the Hamilton cycle problem and other NP-hard problems can be solved in polynomial time when restricted to digraphs of bounded tree-width.

MSC:
05C20 Directed graphs (digraphs), tournaments
05C83 Graph minors
05C85 Graph algorithms (graph-theoretic aspects)
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Arnborg, S.; Corneil, D.G.; Proskurowski, A., Complexity of finding embeddings in a k-tree, SIAM J. alg. disc. & meth., 8, 277-284, (1987) · Zbl 0611.05022
[2] Arnborg, S.; Proskurowski, A., Linear time algorithms for NP-hard problems on graphs embedded in k-trees, Discrete appl. math., 23, 11-24, (1989) · Zbl 0666.68067
[3] Bienstock, D.; Robertson, N.; Seymour, P.D.; Thomas, R., Quickly excluding a forest, J. combin. theory ser. B, 52, 274-283, (1991) · Zbl 0763.05023
[4] Bienstock, D.; Seymour, P.D., Monotonicity in graph searching, J. algorithms, 12, 239-245, (1991) · Zbl 0760.05081
[5] W. Cook, and, P. D. Seymour, An algorithm for the ring-router problem, unpublished manuscript, 1993.
[6] Fortune, S.; Hopcroft, J.E.; Wyllie, J., The directed subgraph homeomorphism problem, J. theoret. comput. sci., 10, 111-121, (1980) · Zbl 0419.05028
[7] Halin, R., S-functions for graphs, J. geometry, 8, 171-186, (1976) · Zbl 0339.05108
[8] Kirousis, L.M.; Papadimitriou, C.H., Interval graphs and searching, Discrete math., 55, 181-184, (1985) · Zbl 0566.05056
[9] Kirousis, L.M.; Papadimitriou, C.H., Searching and pebbling, J. theoret. comput. sci., 47, 205-218, (1986) · Zbl 0616.68064
[10] LaPaugh, A., Recontamination does not help search a graph, Tech. report, (1982) · Zbl 0768.68048
[11] N. Megiddo, S. L. Hakimi, M. R. Garey, D. S. Johnson, and C. H. Papadimitriou, The complexity of searching a graph, in Proceedings of the 22nd FOCS Conference 1981, pp. 376-385. · Zbl 0637.68081
[12] Oporowski, B.; Oxley, J.; Thomas, R., Typical subgraphs of 3- and 4-connected graphs, J. combin. theory ser. B, 57, 239-257, (1993) · Zbl 0728.05041
[13] Parsons, T.D., Pursuit-evasion in a graph, (), 426-441 · Zbl 0379.05026
[14] Reed, B.A., Tree width and tangles: A new connectivity measure and some applications, () · Zbl 0895.05034
[15] Robertson, N.; Seymour, P.D., Graph minors. III. planar tree-width, J. combin. theory ser. B, 36, 49-63, (1984) · Zbl 0548.05025
[16] Robertson, N.; Seymour, P.D., Graph minors. V. excluding a planar graph, J. combin. theory ser. B, 41, 92-114, (1986) · Zbl 0598.05055
[17] Robertson, N.; Seymour, P.D., Graph minors. XIII. the disjoint paths problem, J. combin. theory ser. B, 63, 65-110, (1995) · Zbl 0823.05038
[18] Seymour, P.D.; Thomas, R., Graph searching, and a MIN-MAX theorem for tree-width, J. combin. theory ser. B, 58, 22-33, (1993) · Zbl 0795.05110
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.