Approximating the Spanning k-Tree Forest Problem

DOI10.1007/978-3-642-02270-8_30MaRDI QIDQ5321721zbMATH OpenOpenAlexFDO

Authors 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

\(k\)-treeapproximation algorithmspanning foreststar

Mathematics Subject Classification ID

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

Recommendations

• Approximating the spanning k-tree forest problem
• A 3-approximation algorithm for the maximum leaf \(k\)-forest problem
• Improved Approximation Algorithms for the Spanning Star Forest Problem
• Improved approximation algorithms for the spanning star forest problem
• Leafy spanning \(k\)-forests

Cites work

• R -Domination in Graphs
• \(k\)-tuple domination in graphs
• A linear algorithm for the domination number of a tree
• A note on finding optimum branchings
• A simple derivation of edmonds' algorithm for optimum branchings
• 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
• Edge Dominating Sets in Graphs
• Finding optimum branchings
• scientific article; zbMATH DE number 146666 (Why is no real title available?)
• scientific article; zbMATH DE number 1095172 (Why is no real title available?)
• scientific article; zbMATH DE number 3285076 (Why is no real title available?)
• scientific article; zbMATH DE number 3373559 (Why is no real title available?)
• Improved Approximation Algorithms for the Spanning Star Forest Problem
• Labeling algorithms for domination problems in sun-free chordal graphs
• On the approximability of budgeted allocations and improved lower bounds for submodular welfare maximization and GAP
• Optimum branchings
• Some optimal inapproximability results
• The diversity of domination

Cited in

(16)

• Approximation algorithms for constructing spanning \(K\)-trees using stock pieces of bounded length
• A \(\{-1,0,1\}\)- and sparsest basis for the null space of a forest in optimal time
• Leafy spanning \(k\)-forests
• On approximating tree spanners that are breadth first search trees
• Approximating the spanning star forest problem and its applications to genomic sequence alignment
• On variants of the spanning star forest problem
• Approximating the Spanning Star Forest Problem and Its Application to Genomic Sequence Alignment
• scientific article; zbMATH DE number 1330076 (Why is no real title available?)
• scientific article; zbMATH DE number 1935512 (Why is no real title available?)
• scientific article; zbMATH DE number 742977 (Why is no real title available?)
• Approximating the spanning k-tree forest problem
• Algorithms and Data Structures
• Complexity and approximation of the constrained forest problem
• A local injective proof of log-concavity for increasing spanning forests
• scientific article; zbMATH DE number 7691269 (Why is no real title available?)
• On the SPANNING k-TREE problem

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5321721)