Improved Approximation Algorithms for the Spanning Star Forest Problem
DOI10.1007/978-3-540-74208-1_4zbMATH Open1171.05424OpenAlexW2133372967MaRDI QIDQ3603455FDOQ3603455
Authors: Ning Chen, Roee Engelberg, C. Thach Nguyen, Prasad Raghavendra, Atri Rudra, 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
Recommendations
- Improved approximation algorithms for the spanning star forest problem
- An improved approximation algorithm for spanning star forest in dense graphs
- Improved approximation for spanning star forest in dense graphs
- On variants of the spanning star forest problem
- Approximating the spanning \(k\)-tree forest problem
Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms (68W40) Approximation algorithms (68W25) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)
Cited In (18)
- The maximum weight spanning star forest problem on cactus graphs
- Improved approximation algorithms for the spanning star forest problem
- Approximating the spanning star forest problem and its applications to genomic sequence alignment
- Approximating the Spanning k-Tree Forest Problem
- On the \(k\)-edge-incident subgraph problem and its variants
- On variants of the spanning star forest problem
- An Improved Approximation Bound for Spanning Star Forest and Color Saving
- Approximating the Spanning Star Forest Problem and Its Application to Genomic Sequence Alignment
- Approximating the spanning \(k\)-tree forest problem
- An improved approximation algorithm for spanning star forest in dense graphs
- Weighted upper edge cover: complexity and approximability
- On the approximability of the maximum agreement subtree and maximum compatible tree problems
- Improved approximation for spanning star forest in dense graphs
- Star forests, dominating sets and Ramsey-type problems
- Extended spanning star forest problems
- Complexity and approximability of extended spanning star forest problems in general and complete graphs
- On the star forest polytope for trees and cycles
- Approximation algorithms for the maximum carpool matching problem
This page was built for publication: Improved Approximation Algorithms for the Spanning Star Forest Problem
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3603455)
