×

Exact arborescences, matchings and cycles. (English) Zbl 0632.05047

Given a graph in which each edge has an integral weight, an exact problem is to determine whether a desired structure exists for which the sum of the edge weights is exactly k for some specified k. Given a directed graph with a specified vertex r, an arborescence rooted at r is a set of arcs which induce a connected directed subgraph such that r has indegree zero and all other vertices have indegree one. The existence of polynomial algorithms is shown for exact arborescence, exact spanning tree, exact perfect matching in planar graphs, and exact cycle sum for a class of planar directed graphs.
Reviewer: J.Mitchem

MSC:

05C99 Graph theory
05C20 Directed graphs (digraphs), tournaments
PDF BibTeX XML Cite
Full Text: DOI

References:

[1] Barahona, F., Balancing signed toroidal graphs in polynomial time, (June 1981), Depto. de Matemáticas, Universidad de Chile
[2] Bock, F.C., An algorithm to construct a minimum directed spanning tree in a directed network, (), 29-44
[3] Chaiken, S.; Kleitman, D.J., Matrix tree theorems, J. combin. theory (A), 24, 377-381, (1978) · Zbl 0376.05032
[4] Yoeng-Yin, Chu; Tseng-hong, Liu, On the shortest aborescence of a directed graph, Scientia sinica, 4, 1396, (1965) · Zbl 0178.27401
[5] Edmonds, J., Optimum branchings, J. res. nat. bur. standards (sect. B), 71, 233-240, (1967) · Zbl 0155.51204
[6] Edmonds, J., Systems of distinct representatives and linear algebra, J. res. nat. bur. standards (sect. B), 71, 241-245, (1967) · Zbl 0178.03002
[7] Fulkerson, D.R., Packing rooted directed cuts in a weighted directed graph, Math. programming, 6, 1-13, (1974) · Zbl 0283.05104
[8] Gabow, H.N., A good algorithm for smallest spanning trees with a degree constraint, Networks, 8, 201-208, (1978) · Zbl 0384.90105
[9] Gabow, H.N.; Tarjan, R.E., Efficient algorithms for a family of matroid intersection problems, J. algorithms, 5, 80-131, (1984) · Zbl 0545.05029
[10] Glover, F., The generalized quasi-greedy algorithm for constrained minimum weight matroid bases part I, ()
[11] Glover, F.; Klingman, D., Finding minimum spanning trees with a fixed number of links at a node, (), 111-200 · Zbl 0395.90077
[12] Kasteleyn, P.W., Graph theory and crystal physics, (), 43-110 · Zbl 0205.28402
[13] Papadimitriou, C.H.; Yannakakis, M., The complexity of restricted spanning tree problems, J. ACM, 29, 285-309, (1982) · Zbl 0478.68068
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.