An Improved Approximation Algorithm for Spanning Star Forest in Dense Graphs

DOI10.1007/978-3-642-17461-2_13zbMath1310.68241MaRDI QIDQ3066453

Hongyu Liang, Jing (Selena) He

Publication date: 10 January 2011

Published in: Combinatorial Optimization and Applications (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-17461-2_13

zbMATH Keywords

approximation algorithm; dense graphs; spanning star forest

Mathematics Subject Classification ID

05C05: Trees

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

05C85: Graph algorithms (graph-theoretic aspects)

68W25: Approximation algorithms

Related Items

APPROXIMATING THE SPANNING k-TREE FOREST PROBLEM, On Variants of the Spanning Star Forest Problem