Algorithms — ESA 2002
Lecture Notes in Computer Science, 2002, Volume 2461/2002, 686-698, DOI: 10.1007/3-540-45749-6_60

Approximation Algorithm for the Maximum Leaf Spanning Tree Problem for Cubic Graphs

Krzysztof Loryś and Grażyna Zwoźniak

View Related Documents

Abstract

The problem of finding spanning trees with maximal number of leaves is considered. We present a linear-time algorithm for cubic graphs that achieves approximation ratio 7/4. The analysis of the algorithm uses a kind of the accounting method, that is of independent interest.
partially supported by Komitet Badań Naukowych, grant 8 T11C 044 19

Fulltext Preview

Image of the first page of the fulltext document