Approximating the spanning k-tree forest problem

DOI10.1142/S0129054112500232MaRDI QIDQ4923297zbMATH OpenFDO

Authors Chung-Shou Liao, Louxin Zhang

Publication date 6 June 2013

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

Full work available at URL https://doi.org/10.1142/S0129054112500232

zbMATH Keywords

(directed) \(k\)-tree forestsapproximation algorithmsdominating setstar forests

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) 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
• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
• A note on finding optimum branchings
• A simple derivation of edmonds' algorithm for optimum branchings
• An improved approximation algorithm for spanning star forest in dense graphs
• An Improved Approximation Bound for Spanning Star Forest and Color Saving
• 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
• Finding optimum branchings
• Graph minors. II. Algorithmic aspects of tree-width
• Improved Approximation Algorithms for the Spanning Star Forest Problem
• On the approximability of budgeted allocations and improved lower bounds for submodular welfare maximization and GAP
• On variants of the spanning star forest problem
• Solving huge size instances of the optimal diversity management problem
• The diversity of domination

Cited in

(23)

• A \(\{-1,0,1\}\)- and sparsest basis for the null space of a forest in optimal time
• Improved approximation for spanning star forest in dense graphs
• Leafy spanning \(k\)-forests
• Improved approximation algorithms for the spanning star forest problem
• A 3-approximation algorithm for the maximum leaf \(k\)-forest problem
• Complexity and approximability of extended spanning star forest problems in general and complete graphs
• 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
• An improved approximation algorithm for spanning star forest in dense graphs
• 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
• 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?)
• The maximum weight spanning star forest problem on cactus graphs
• 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 Q4923297)