APPROXIMATING THE SPANNING k-TREE FOREST PROBLEM

DOI10.1142/S0129054112500232zbMath1264.68087MaRDI QIDQ4923297

Louxin Zhang, Chung-Shou Liao

Publication date: 6 June 2013

Published in: International Journal of Foundations of Computer Science (Search for Journal in Brave)

zbMATH Keywords

dominating set; approximation algorithms; star forests; (directed) \(k\)-tree forests

Mathematics Subject Classification ID

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

05C85: Graph algorithms (graph-theoretic aspects)

68W25: Approximation algorithms

Cites Work

• Solving huge size instances of the optimal diversity management problem
• The diversity of domination
• On Variants of the Spanning Star Forest Problem
• 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
• 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
• Graph minors. II. Algorithmic aspects of tree-width
• Approximation schemes for covering and packing problems in image processing and VLSI
• A note on finding optimum branchings
• R -Domination in Graphs
• Finding optimum branchings
• A simple derivation of edmonds' algorithm for optimum branchings
• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth