https://scholars.lib.ntu.edu.tw/handle/123456789/634441
標題: | A Simple 2 -Approximation for Maximum-Leaf Spanning Tree | 作者: | Liao, I. Cheng HSUEH-I LU |
關鍵字: | Approximation algorithms | maximum-leaf spanning tree; Computer Science - Data Structures and Algorithms; Computer Science - Data Structures and Algorithms; 05C38, 05C10, 05C85, 68P05 | 公開日期: | 1-一月-2023 | 來源出版物: | International Journal of Foundations of Computer Science | 摘要: | For an m-edge connected simple graph G, finding a spanning tree of G with the maximum number of leaves is MAXSNP-complete. The problem remains NP-complete even if G is planar and the maximal degree of G is at most four. Lu and Ravi gave the first known polynomial-time approximation algorithms with approximation factors 5 and 3. Later, they obtained a 3-approximation algorithm that runs in near-linear time. The best known result is Solis-Oba, Bonsma, and Lowski's O(m)-time 2-approximation algorithm. We show an alternative simple O(m)-time 2-approximation algorithm whose analysis is simpler. This paper is dedicated to the cherished memory of our dear friend, Professor Takao Nishizeki. |
描述: | 10 pages, 4 figures |
URI: | https://scholars.lib.ntu.edu.tw/handle/123456789/634441 | ISSN: | 01290541 | DOI: | 10.1142/S0129054123420029 |
顯示於: | 資訊工程學系 |
在 IR 系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。