Let fm,n,h be the number of spanning forests with h edges in the complete bipartite graph Km,n. Kirchhoff\textquoterights Matrix Tree Theorem implies fm,n,m+n-1=mn-1 nm-1 when m ≥1 and n ≥1, since fm,n,m+n-1 is the number of spanning trees in Km,n. In this paper, we give an algorithm for computing fm,n,h for general m,n,h. We implement this algorithm and use it to compute all non-zero fm,n,h when m ≤50 and n ≤50 in under 2 days.

Source : oai:HAL:hal-01179216v1

Volume: Vol. 16 no. 1

Section: Analysis of Algorithms

Published on: May 12, 2014

Submitted on: October 6, 2012

Keywords: [INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM]

This page has been seen 152 times.

This article's PDF has been downloaded 477 times.