×

Counting minimum weight arborescences. (English) Zbl 1401.05280

Algorithmica 80, No. 12, 3908-3919 (2018); erratum ibid. 81, No. 1, 418 (2019).
Summary: In a directed graph \(D = (V, A)\) with a specified vertex \(r \in V\), an arc subset \(B\subseteq A\) is called an \(r\)-arborescence if \(B\) has no arc entering \(r\) and there is a unique path from \(r\) to \(v\) in \((V,B)\) for each \(v \in V \setminus \{ r \}\). The problem of finding a minimum weight \(r\)-arborescence in a weighted digraph has been studied for decades starting with Y.-j. Chu and T.-h. Liu [Sci. Sin. 14, 1396–1400 (1965; Zbl 0178.27401)], J. Edmonds [J. Res. Natl. Bur. Stand., Sect. B 71, 233–240 (1967; Zbl 0155.51204)] and F. Bock [in: Developments Operations Res. 1, Proc. 3rd annual Israel Conf. Operations Res. 1969, 29–44 (1971; Zbl 0235.90056)]. In this paper, we focus on the number of minimum weight arborescences. We present an algorithm for counting minimum weight \(r\)-arborescences in \(O(n^{\omega})\) time, where \(n\) is the number of vertices of an input digraph and \(\omega\) is the matrix multiplication exponent.

MSC:

05C85 Graph algorithms (graph-theoretic aspects)
05C20 Directed graphs (digraphs), tournaments
PDF BibTeX XML Cite
Full Text: DOI

References:

[1] Bock, F.; Avi-Itzhak, B. (ed.), An algorithm to construct a minimum directed spanning tree in a directed network, 29-44, (1971), New York
[2] Broder, AZ; Mayr, EW, Counting minimum weight spanning trees, J. Algorithms, 24, 171-176, (1997) · Zbl 0882.68107
[3] Chu, Y.; Liu, T., On the shortest arborescence of a directed graph, Sci. Sin., 14, 1396-1400, (1965) · Zbl 0178.27401
[4] Edmonds, J., Optimal branchings, J. Res. Natl. Bur. Stand., 71B, 233-240, (1967) · Zbl 0155.51204
[5] Fulkerson, DR, Packing rooted directed cuts in a weighted directed graph, Math. Program., 6, 1-13, (1974) · Zbl 0283.05104
[6] Gabow, HN; Galil, Z.; Spencer, T.; Tarjan, RE, Efficient algorithms for finding minimum spanning trees in undirected and directed graphs, Combinatrica, 6, 109-122, (1986) · Zbl 0608.05027
[7] Lovász, L.: Combinatorial Problems and Exercises, 2nd edn. AMS Chelsea Publishing, Providence (2007) · Zbl 1120.05001
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.