Approximating the Spanning k-Tree Forest Problem

DOI10.1007/978-3-642-02270-8_30zbMath1248.68562MaRDI QIDQ5321721

Chung-Shou Liao, Louxin Zhang

Publication date: 14 July 2009

Published in: Frontiers in Algorithmics (Search for Journal in Brave)

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

zbMATH Keywords

approximation algorithm; \(k\)-tree; star; spanning forest

Mathematics Subject Classification ID

68R10: Graph theory (including graph drawing) in computer science

68W25: Approximation algorithms

Related Items

On Variants of the Spanning Star Forest Problem

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• \(k\)-tuple domination in graphs
• Labeling algorithms for domination problems in sun-free chordal graphs
• A linear algorithm for the domination number of a tree
• The diversity of domination
• On the Approximability of Budgeted Allocations and Improved Lower Bounds for Submodular Welfare Maximization and GAP
• Improved Approximation Algorithms for the Spanning Star Forest Problem
• Approximating the Spanning Star Forest Problem and Its Application to Genomic Sequence Alignment
• Approximation schemes for covering and packing problems in image processing and VLSI
• A note on finding optimum branchings
• Edge Dominating Sets in Graphs
• R -Domination in Graphs
• Finding optimum branchings
• Some optimal inapproximability results
• Optimum branchings
• A simple derivation of edmonds' algorithm for optimum branchings