Improved Approximation Algorithms for the Spanning Star Forest Problem

DOI10.1007/978-3-540-74208-1_4zbMath1171.05424OpenAlexW2133372967MaRDI QIDQ3603455

Prasad Raghavendra, Atri Rudra, Roee Engelberg, C. Thach Nguyen, Ning Chen, Gyanit Singh

Publication date: 17 February 2009

Published in: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (Search for Journal in Brave)

Full work available at URL: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.121.1999

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Approximation algorithms (68W25)

Related Items (10)

An Improved Approximation Bound for Spanning Star Forest and Color Saving ⋮ Approximation algorithms for the maximum carpool matching problem ⋮ Approximating the Spanning k-Tree Forest Problem ⋮ Improved approximation for spanning star forest in dense graphs ⋮ On the \(k\)-edge-incident subgraph problem and its variants ⋮ On Variants of the Spanning Star Forest Problem ⋮ APPROXIMATING THE SPANNING k-TREE FOREST PROBLEM ⋮ On the star forest polytope for trees and cycles ⋮ Weighted Upper Edge Cover: Complexity and Approximability ⋮ On the approximability of the maximum agreement subtree and maximum compatible tree problems

This page was built for publication: Improved Approximation Algorithms for the Spanning Star Forest Problem