Improved approximation for spanning star forest in dense graphs

DOI10.1007/S10878-012-9499-2MaRDI QIDQ1944390zbMATH OpenOpenAlexFDO

Authors 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

zbMATH Keywords

approximation algorithmdense graphhardness of approximationspanning star forest

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Approximation methods and heuristics in mathematical programming (90C59)

Recommendations

• An improved approximation algorithm for spanning star forest in dense graphs
• Improved approximation algorithms for the spanning star forest problem
• Improved Approximation Algorithms for the Spanning Star Forest Problem
• On variants of the spanning star forest problem
• Approximating the spanning k-tree forest problem

Cites work

• A threshold of ln n for approximating set cover
• An Improved Approximation Bound for Spanning Star Forest and Color Saving
• Approximating subdense instances of covering problems
• Approximating the Spanning Star Forest Problem and Its Application to Genomic Sequence Alignment
• Approximating vertex cover on dense graphs
• Chebyshev's approximation algorithms and applications
• Computing and Combinatorics
• Exponential time algorithms for the \textsc{minimum dominating set} problem on some graph classes
• scientific article; zbMATH DE number 1559563 (Why is no real title available?)
• Improved Approximation Algorithms for the Spanning Star Forest Problem
• Improved approximation bounds for edge dominating set in dense graphs
• On the approximability of budgeted allocations and improved lower bounds for submodular welfare maximization and GAP
• Polynomial time approximation schemes for dense instances of \( \mathcal{NP}\)-hard problems
• Problems remaining NP-complette for sparse or dense graphs

Cited in

(6)

• Improved approximation algorithms for the spanning star forest problem
• Complexity and approximability of extended spanning star forest problems in general and complete graphs
• On variants of the spanning star forest problem
• An improved approximation algorithm for spanning star forest in dense graphs
• Improved Approximation Algorithms for the Spanning Star Forest Problem
• Weighted upper edge cover: complexity and approximability

This page was built for publication: Improved approximation for spanning star forest in dense graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1944390)