A 2-Approximation Algorithm for Finding a Spanning Tree with Maximum Number of Leaves

详细信息    查看全文

• 作者：Roberto Solis-Oba ; Paul Bonsma ; Stefanie Lowski
• 关键词：Approximation ; Algorithm ; Graphs ; Optimization
• 刊名：Algorithmica
• 出版年：2017
• 出版时间：February 2017
• 年：2017
• 卷：77
• 期：2
• 页码：374-388
• 全文大小：
• 刊物类别：Computer Science
• 刊物主题：Algorithm Analysis and Problem Complexity; Theory of Computation; Mathematics of Computing; Algorithms; Computer Systems Organization and Communication Networks; Data Structures, Cryptology and Inform
• 出版者：Springer US
• ISSN：1432-0541
• 卷排序：77

文摘

We study the problem of finding a spanning tree with maximum number of leaves. We present a simple, linear time 2-approximation algorithm for this problem, improving on the previous best known algorithm for the problem, which has approximation ratio 3.