Deeper Local Search for Better Approximation on Maximum Internal Spanning Trees Conference Paper uri icon

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

published proceedings

  • Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

author list (cited authors)

  • Li, W., Chen, J., & Wang, J.

citation count

  • 9

complete list of authors

  • Li, Wenjun||Chen, Jianer||Wang, Jianxin

publication date

  • January 2014