| Presentation | 2001/1/17 A Consideration of approximate algorithms for finding Maximum Leaf Spanning Tree based on the degree of a vertex/edge Daisuke Mori, Toshio Koide, Hitoshi Watanabe, |
|---|---|
| PDF Download Page | PDF download Page Link |
| Abstract(in Japanese) | (See Japanese page) |
| Abstract(in English) | 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. |
| Keyword(in Japanese) | (See Japanese page) |
| Keyword(in English) | Maximum Leaf Spanning Tree / graph theory / elementary transformation / degree of vertex/edge / approximate search algorith |
| Paper # | CAS2000-91 |
| Date of Issue |
| Conference Information | |
| Committee | CAS |
|---|---|
| Conference Date | 2001/1/17(1days) |
| Place (in Japanese) | (See Japanese page) |
| Place (in English) | |
| Topics (in Japanese) | (See Japanese page) |
| Topics (in English) | |
| Chair | |
| Vice Chair | |
| Secretary | |
| Assistant | |
| Paper Information | |
| Registration To | Circuits and Systems (CAS) |
|---|---|
| Language | JPN |
| Title (in Japanese) | (See Japanese page) |
| Sub Title (in Japanese) | (See Japanese page) |
| Title (in English) | A Consideration of approximate algorithms for finding Maximum Leaf Spanning Tree based on the degree of a vertex/edge |
| Sub Title (in English) | |
| Keyword(1) | Maximum Leaf Spanning Tree |
| Keyword(2) | graph theory |
| Keyword(3) | elementary transformation |
| Keyword(4) | degree of vertex/edge |
| Keyword(5) | approximate search algorith |
| 1st Author's Name | Daisuke Mori |
| 1st Author's Affiliation | Graduate School of Engineering, Soka University() |
| 2nd Author's Name | Toshio Koide |
| 2nd Author's Affiliation | Graduate School of Engineering, Soka University |
| 3rd Author's Name | Hitoshi Watanabe |
| 3rd Author's Affiliation | Graduate School of Engineering, Soka University |
| Date | 2001/1/17 |
| Paper # | CAS2000-91 |
| Volume (vol) | vol.100 |
| Number (no) | 573 |
| Page | pp.pp.- |
| #Pages | 4 |
| Date of Issue | |