A consideration of approximate algorithms for finding maximum leaf spanning tree based on the degree of a vertex/edge

摘要

This paper proposed and investigated algorithms for finding maximum leaf spanning tree (MLST). Since the tree finding problem is NP complete, simple elementary transformation is not useful. This paper defined leaf increasing elementary transformation and applied it to MLST search. Utilizing newly defined vertex degree and edge degree, several algorithms for finding MLST are also proposed. Investigating many examples of MLST search, it turns out that LDFS-Tree (large-Degree-First-Search-Tree) algorithm is more effective than other proposed algorithms.