An Algorithm to Find the First K Spanning Trees with Minimum Weights

Gang Ming Sun; Hong Li; Pin Wang

doi:10.4028/www.scientific.net/AMM.721.535

Paper Titles

Research on Identification of Induction Motor Parameters Based on Nameplate Data
p.517

Research on Wireless Temperature Measurement System for Electrical Equipment
p.523

The Design of Mobile Phone Multimeter Based on the Android Platform
p.527

Application of the Bat Algorithm to Optimize the BP Neural Network
p.531

An Algorithm to Find the First K Spanning Trees with Minimum Weights
p.535

The Multi-Site Joint Operation Method Based on Discharge Gate Ant Colony Algorithm
p.539

A Novel and Improved Apriori Algorithm
p.543

Algorithm for Computing Attribute Reduction Based on Radix Sort of Optimized Linked List Structure
p.547

Impact of DLC on Distribution System Reliability
p.555

HomeApplied Mechanics and MaterialsApplied Mechanics and Materials Vol. 721An Algorithm to Find the First K Spanning Trees...

An Algorithm to Find the First K Spanning Trees with Minimum Weights

Abstract:

By improving and extended Kruskal algorithm and using the backtracking method, we obtain an algorithm to find the first k spanning trees with minimum weights. Experiments show that for various types of randomly generated undirected connected graphs of which the number of nodes is 10,000, while the number of edges can be up to millions, this algorithm can obtain results within a few seconds.

You might also be interested in these eBooks

Vehicle, Mechanical and Electrical Engineering

View Preview

Info:

Periodical:

Applied Mechanics and Materials (Volume 721)

Pages:

535-538

DOI:

https://doi.org/10.4028/www.scientific.net/AMM.721.535

Citation:

Cite this paper

Online since:

December 2014

Authors:

Gang Ming Sun, Hong Li, Pin Wang*

Keywords:

Backtracking, Connected Graph, Kruskal Algorithm, Minimum Spanning Tree, Spanning Tree

Export:

RIS, BibTeX

Price:

Permissions CCC:

Request Permissions

Permissions PLS:

Request Permissions

Сopyright:

Citation:

* - Corresponding Author

References

[1] Dong Yuehua; Li Yunhao; Jiang Zaidong. Implement Prim Algorithm with Broken Cycle Approach. Journal of Jiangxi University of Science and Technology. 2008. 20-22.

Google Scholar

[2] Du Lingling. The Application of Improved Prim algorithm in GIS. Mapping Information and Engineering. 2006. 28-29.

Google Scholar

[3] Han Lixia; Wang Yuping. The New Genetic Algorithm to Solve the Degree-constrained Minimum Spanning Tree. Computer Engineering and Application. 2006. 13-15.

Google Scholar

[4] Duan Zhi; Yuan Zhenzhou. Solving Method for Maximum Spanning Tree of the Importance of rural Highway Network Layout Based on Prim algorithm. Highway. 2007. 111-114.

Google Scholar

[5] Yang Chenghui; Yin Hong; Meng Jianjun; Jiang Huqiang. Simulation Study and Application on Communication Network setup Based on Prim Algorithm. The Computer Simulation. 2007. 144-147.

Google Scholar

[6] Li Guoqi. PRIM Method of Minimum Spanning Tree of Undirected Weighted Graph Based on the Heap. Computer Learning. 2007. 61-62.

Google Scholar

[7] Liu Pingyuan; Zhang Ni. Alternate Solution for Prim Algorithm. Scientific Chinese. 2007. 125-126.

Google Scholar