An algorithm to generate all spanning trees of a graph in order of increasing cost

An algorithm to generate all spanning trees of a graph in order of increasing cost

0.00 Avg rating0 Votes
Article ID: iaor2009601
Country: Brazil
Volume: 25
Issue: 2
Start Page Number: 219
End Page Number: 229
Publication Date: May 2005
Journal: Pesquisa Operacional
Authors: ,
Abstract:

A minimum spanning tree of an undirected graph can be easily obtained using classical algorithms by Prim or Kruskal. A number of algorithms have been proposed to enumerate all spanning trees of an undirected graph. Good time and space complexities are the major concerns of these algorithms. Most algorithms generate spanning trees using some fundamental cut or circuit. In the generation process, the cost of the tree is not taken into consideration. This paper presents an algorithm to generate spanning trees of a graph in order of increasing cost.

Reviews

Required fields are marked *. Your email address will not be published.