×

Counting \(k\)-component forests of a graph. (English) Zbl 0773.90084

We describe an algorithm for computing the number of \(k\)-component spanning forests of a graph \(G\) which runs in polynomial time for fixed \(k\). The algorithm is based on earlier work by C. I. Liu and Y. Chow [Acta Math. Hung. 41, 27-36 (1983; Zbl 0517.05044)]. Our contributions are a simpler graph-theoretic proof of their formula, and a demonstration of how Jacobi’s Theorem can be applied to improve the asymptotic time complexity. By matroid duality, the number of connected spanning subgraphs of cyclomatic number \(c\) of a planar graph equals the number of \(c+1\)-component forests in the dual. Thus one application of this research is an algorithm for counting connected spanning unicyclic subgraphs of a planar graph. We show this can be done in time \(O(M(n))\) where \(M(n)\) is the time complexity of multiplying together two \(n\) by \(n\) matrices.
Remark: In Corollary 4.1, the first term of the equation should be premultiplied by \(\text{det}(A)\).

MSC:

90C35 Programming involving graphs or networks
05C85 Graph algorithms (graph-theoretic aspects)
90C60 Abstract computational complexity for mathematical programming problems
90B25 Reliability, availability, maintenance, inspection in operations research
90-08 Computational methods for problems pertaining to operations research and mathematical programming
05C50 Graphs and linear algebra (matrices, eigenvalues, etc.)

Citations:

Zbl 0517.05044
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] , and , The Design and Analysis of Computer Algorithms. Addison-Wesley, Reading, MA (1974).
[2] and , Graph Theory with Applications. Elsevier North-Holland, New York (1976). · Zbl 1226.05083
[3] The Combinatorics of Network Reliability. The International Series of Monographs on Computer Science. Oxford University Press, New York (1987).
[4] and , Matrix multiplications via arithmetic progressions. 19th Annual STOC (1987) 1–6.
[5] Algorithmic Graph Theory. Cambridge University Press, New York (1985).
[6] Hopcroft, JACM 21 pp 549– (1974)
[7] The Theory of Matrices in Numerical Analysis. Blaisdell, Toronto (1964).
[8] Liu, Proceed. Am. Math. Soc. 83 pp 659– (1981)
[9] Liu, Acta Math. Hung. 41 pp 27– (1983)
[10] Ramesh, Ann. Discrete Math. 33 pp 261– (1987)
[11] Richter, J. Graph Theory 8 pp 365– (1984)
[12] Linear Algebra and Its Applications. Academic Press, New York (1976).
[13] Strassen, Numerische Math. 13 pp 354– (1974)
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.