On Variants of the Spanning Star Forest Problem

DOI10.1007/978-3-642-21204-8_11zbMath1329.68140MaRDI QIDQ3004657

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

68Q25: Analysis of algorithms and problem complexity

05C05: Trees

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

68W25: Approximation algorithms

Related Items

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

Cites Work

• Unnamed Item
• Polynomial time approximation schemes for dense instances of \( \mathcal{NP}\)-hard problems
• Complexity of approximating bounded variants of optimization problems
• An Improved Approximation Algorithm for Spanning Star Forest in Dense Graphs
• 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
• Approximating the Spanning k-Tree Forest Problem
• Computing and Combinatorics
• On the complexity of \(k\)-SAT