Most, And Least, Compact Spanning Trees of a Graph

Gyan Ranjan, Nishant Saurabh, Amit Ashutosh

Research output: Working paperPreprintAcademic

Abstract

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) \in \mathcal{T}(G)$ to be considered $T^*(G)$, where $\mathcal{T}(G)$ represents the set of all the spanning trees of the graph $G$, it must have the least sum of inter-vertex pair shortest path distances from amongst the members of the set $\mathcal{T}(G)$. Similarly, for it to be considered $T^\#(G)$, it must have the highest sum of 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; and discuss potentials for computational efficiencies, along with relevant trade-offs, to enable the extraction of $T^*(G)$ and $T^\#(G)$ within reasonable time limits on standard platforms.
Original languageEnglish
Pages1-15
DOIs
Publication statusPublished - 14 Jun 2022

Keywords

  • Spanning Sub-Graph
  • Minimum Spanning Tree
  • Prim’s Algorithm
  • Kruskal’s Algorithm
  • Forest Matrix
  • Forest Distance
  • Compact Spanning Tree

Fingerprint

Dive into the research topics of 'Most, And Least, Compact Spanning Trees of a Graph'. Together they form a unique fingerprint.

Cite this