DocumentCode
3034245
Title
A minimum spanning tree algorithm based on binary coding
Author
Wang, Fangxiu
Author_Institution
Dept. of Math. & Phys., Wuhan Polytech. Univ., Wuhan, China
fYear
2011
fDate
26-28 July 2011
Firstpage
5227
Lastpage
5229
Abstract
We can only get a minimum spanning tree from all the spanning trees with the current minimum spanning tree algorithm, So we hope to present a new algorithm to improve it. The new algorithm is mainly use the binary code and the characteristics of the minimum spanning tree to get all the minimum spanning trees. At first, It eliminates some of the non spanning trees according to the number of the graph edges. What is more, It eliminates some of the non-spanning trees according to the judgement of the graph connectivity. In fact, the nature of the algorithm is to look for the best in the global scope. At last, we can find all the minimum spanning trees of the connected graph in view of the algorithm. An example shows that the algorithm has clear steps, convenient program implementation and general good characteristic.
Keywords
binary codes; trees (mathematics); binary code; binary coding; graph connectivity; graph edges; minimum spanning tree algorithm; Algorithm design and analysis; Assembly; Binary codes; Data structures; Graph theory; Physics; Binary code; Connected graph; Minimum spanning tree; algorithm; chromosome;
fLanguage
English
Publisher
ieee
Conference_Titel
Multimedia Technology (ICMT), 2011 International Conference on
Conference_Location
Hangzhou
Print_ISBN
978-1-61284-771-9
Type
conf
DOI
10.1109/ICMT.2011.6002283
Filename
6002283
Link To Document