• 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