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

摘要

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.