2005/05/22 by Naveen Garg · 1 citation
Computer Science · Mathematics · #Advanced Graph Theory Research #Computational Geometry and Mesh Generation #Data Management and Algorithms #Approximation algorithm #Combinatorics #Mathematics #k-minimum spanning tree #Tree (set theory) #Time complexity #Minimum spanning tree #Upper and lower bounds #Discrete mathematics #K-ary tree #Tree structure #Binary tree
paper · doi:10.1145/1060590.1060650
openalex publication_date 2005/05/22 · openalex created_date 2016/06/24 · openalex updated_date 2026/07/29
We present a polynomial time 2-approximation algorithm for the problem of finding the minimum tree that spans at least k vertices. Our result also leads to a 2-approximation algorithm for finding the minimum tour that visits k vertices and to a 3-approximation algorithm for the problem of finding the maximum number of vertices that can be spanned by a tree of length at most a given bound.