Improved Approximation Algorithms for the Spanning Star Forest Problem

DOI10.1007/978-3-540-74208-1_4MaRDI QIDQ3603455zbMATH OpenOpenAlexFDO

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

Mathematics Subject Classification ID

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)

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

Cited in

(18)

• Approximation algorithms for the maximum carpool matching problem
• 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
• On the approximability of the maximum agreement subtree and maximum compatible tree problems
• Weighted upper edge cover: complexity and approximability
• 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

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)