Most, And Least, Compact Spanning Trees of a Graph
share
We introduce the concept of Most, and Least, Compact Spanning Trees - denoted respectively by T^*(G) and T^#(G) - of a simple, connected, undirected and unweighted graph G(V, E, W). For a spanning tree T(G) ∈𝒯(G) to be considered T^*(G), where 𝒯(G) represents the set of all the spanning trees of the graph G, it must have the least average inter-vertex pair (shortest path) distances from amongst the members of the set 𝒯(G). Similarly, for it to be considered T^#(G), it must have the highest average inter-vertex pair (shortest path) distances. In this work, we present an iteratively greedy rank-and-regress method that produces at least one T^*(G) or T^#(G) by eliminating one extremal edge per iteration. The rank function for performing the elimination is based on the elements of the matrix of relative forest accessibilities of a graph and the related forest distance. We provide empirical evidence in support of our methodology using some standard graph families: complete graphs, the Erdős-Renyi random graphs and the Barabási-Albert scale-free graphs; and discuss computational complexity of the underlying methods which incur polynomial time costs.
READ FULL TEXT