Approximating the Spanning k-Tree Forest Problem

DOI10.1007/978-3-642-02270-8_30zbMath1248.68562OpenAlexW1606114348MaRDI 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\)-treestarspanning forest

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25)

Related Items (1)

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

This page was built for publication: Approximating the Spanning k-Tree Forest Problem