Improved approximation for spanning star forest in dense graphs
From MaRDI portal
Publication:1944390
DOI10.1007/s10878-012-9499-2zbMath1268.90114OpenAlexW2033780447MaRDI QIDQ1944390
Hongyu Liang, Jing (Selena) He
Publication date: 25 March 2013
Published in: Journal of Combinatorial Optimization (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s10878-012-9499-2
Programming involving graphs or networks (90C35) Approximation methods and heuristics in mathematical programming (90C59)
Related Items (2)
Complexity and approximability of extended spanning star forest problems in general and complete graphs ⋮ Weighted Upper Edge Cover: Complexity and Approximability
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Improved approximation bounds for edge dominating set in dense graphs
- Polynomial time approximation schemes for dense instances of \( \mathcal{NP}\)-hard problems
- Approximating Subdense Instances of Covering Problems
- On the Approximability of Budgeted Allocations and Improved Lower Bounds for Submodular Welfare Maximization and GAP
- A threshold of ln n for approximating set cover
- An Improved Approximation Bound for Spanning Star Forest and Color Saving
- Improved Approximation Algorithms for the Spanning Star Forest Problem
- Approximating the Spanning Star Forest Problem and Its Application to Genomic Sequence Alignment
- Problems remaining NP-complette for sparse or dense graphs
- Computing and Combinatorics
- Chebyshev's approximation algorithms and applications
This page was built for publication: Improved approximation for spanning star forest in dense graphs
