On Variants of the Spanning Star Forest Problem

DOI10.1007/978-3-642-21204-8_11zbMath1329.68140OpenAlexW170534829MaRDI 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

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

Related Items (4)

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

This page was built for publication: On Variants of the Spanning Star Forest Problem