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


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


[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, (Avi-Itzhak, B., Developments in Operations Research (1971), Gordon and Breach: Gordon and Breach New York), 29-44 · Zbl 0235.90056
[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, (MSIS report 84-5 (May 1984), University of Colorado)
[11] Glover, F.; Klingman, D., Finding minimum spanning trees with a fixed number of links at a node, (Roy, B., Combinatorial Programming: Methods and Applications (1974), Reidel: Reidel Dordrecht), 111-200 · Zbl 0395.90077
[12] Kasteleyn, P. W., Graph theory and crystal physics, (Harary, F., Graph Theory and Theoretical Physics (1967), Academic Press: Academic Press London), 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. 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.