On variants of the spanning star forest problem

DOI10.1007/978-3-642-21204-8_11MaRDI QIDQ3004657zbMATH OpenOpenAlexFDO

Authors Hongyu Liang, Jing (Selena) He

Publication date 3 June 2011

Published in Frontiers in Algorithmics and Algorithmic Aspects in Information and Management (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-21204-8_11

Mathematics Subject Classification ID

Trees (05C05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25) Approximation algorithms (68W25)

Recommendations

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

Cites work

• A threshold of ln n for approximating set cover
• An improved approximation algorithm for spanning star forest in dense graphs
• An Improved Approximation Bound for Spanning Star Forest and Color Saving
• Approximating the Spanning k-Tree Forest Problem
• Approximating the Spanning Star Forest Problem and Its Application to Genomic Sequence Alignment
• Complexity of approximating bounded variants of optimization problems
• Computing and Combinatorics
• scientific article; zbMATH DE number 1839431 (Why is no real title available?)
• Improved Approximation Algorithms for the Spanning Star Forest Problem
• On the approximability of budgeted allocations and improved lower bounds for submodular welfare maximization and GAP
• On the complexity of k-SAT
• Polynomial time approximation schemes for dense instances of \( \mathcal{NP}\)-hard problems

Cited in

(15)

• Extended spanning star forest problems
• Star-factors in graphs with large minimum degree
• Improved approximation for spanning star forest in dense graphs
• Improved approximation algorithms for the spanning star forest problem
• Complexity and approximability of extended spanning star forest problems in general and complete graphs
• The complete optimal stars-clustering-tree problem
• An improved approximation algorithm for spanning star forest in dense graphs
• Some Variants of the Star Height Problem
• An Improved Approximation Bound for Spanning Star Forest and Color Saving
• On the Optimal Stars Clustering Tree Problem
• Improved Approximation Algorithms for 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
• The maximum weight spanning star forest problem on cactus graphs

This page was built for publication: On variants of the spanning star forest problem

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