IJPAM: Volume 106, No. 8 (2016)

SOLVING SPANNING TREE PROBLEMS IN
A CONNECTED WEIGHTED SIMPLE GRAPH

S. Kalidasan$^1$, P. Pandian$^2$
$^{1,2}$Department of Mathematics
School of Advanced Sciences
VIT University, Vellore-14, INDIA


Abstract. In this paper, a new algorithm namely, spread search algorithm is proposed for finding a maximum/minimum spanning tree of a given weighted connected simple graph. The proposed algorithm differs from the existing algorithms and it has the time complexity of $O((m-k)^2)$ where m is the number of edges and $k$ is the number of pendant edges in the given graph. Numerical examples are presented for illustrating the solution procedure of the spread search algorithm.

Received: February 15, 2016

AMS Subject Classification: 68R10, 05C05, 05C85

Key Words and Phrases: graph, weighted graph, maximumn spanning tree, spread search algorithm

Download paper from here.



DOI: 10.12732/ijpam.v106i8.10 How to cite this paper?

Source: International Journal of Pure and Applied Mathematics
ISSN printed version: 1311-8080
ISSN on-line version: 1314-3395
Year: 2016
Volume: 106
Issue: 8
Pages: 67 - 72


Google Scholar; DOI (International DOI Foundation); WorldCAT.

CC BY This work is licensed under the Creative Commons Attribution International License (CC BY).