Deeper Local Search for Better Approximation on Maximum Internal Spanning Trees
Conference Paper
Overview
Identity
Additional Document Info
Other
View All
Overview
abstract
Spanning tree has been fundamental in the research of graph algorithms. In this paper, we study the optimization problem MaxIST, which maximizes the number of internal nodes in a spanning tree of a given graph, and is a generalization of the famous Hamiltonian-Path problem. We present a polynomial-time approximation algorithm based on a deep local search strategy, identify combinatorial structures that support thorough analysis on the spanning trees resulted from such deep local search strategies, and prove that our algorithm has an approximation ratio 1.5 for the MaxIST problem, improving the previous best approximation algorithm of ratio 5/3 for the problem. 2014 Springer-Verlag Berlin Heidelberg.
name of conference
Algorithms - ESA 2014 - 22th Annual European Symposium, Wroclaw, Poland, September 8-10, 2014. Proceedings