Complexity and approximation of the constrained forest problem

DOI10.1016/J.TCS.2010.07.018zbMATH Open1217.68110OpenAlexW2039500680MaRDI QIDQ553340FDOQ553340

Authors Cristina Bazgan, Basile Couëtoux, Zsolt Tuza

Publication date 27 July 2011

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2010.07.018

zbMATH Keywords

complexitytreewidthapproximationAPX-hardnessplanar graphsbipartite graphsconstrained forestptas

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Recommendations

• A General Approximation Technique for Constrained Forest Problems
• scientific article; zbMATH DE number 742977
• A class of heuristics for the constrained forest problem
• A \(\frac{3}{2}\) approximation for a constrained forest problem
• Another greedy heuristic for the constrained forest problem
• Computational Complexity of a Cost Allocation Approach to a Fixed Cost Spanning Forest Problem
• Approximating the Spanning k-Tree Forest Problem
• Approximating the spanning \(k\)-tree forest problem
• Covering a graph with a constrained forest (extended abstract)
• The maximum agreement forest problem: Approximation algorithms and computational experiments

Cites work

• scientific article; zbMATH DE number 3154393 (Why is no real title available?)
• scientific article; zbMATH DE number 3862930 (Why is no real title available?)
• A General Approximation Technique for Constrained Forest Problems
• A class of heuristics for the constrained forest problem
• A greedy heuristic for a minimum-weight forest problem
• A partial k-arboretum of graphs with bounded treewidth
• Algorithms – ESA 2005
• Another greedy heuristic for the constrained forest problem
• Approximation algorithms for NP-complete problems on planar graphs
• Complexity of approximating bounded variants of optimization problems
• Extensions of Gallai's graph covering theorems for uniform hypergraphs
• Graph minors. X: Obstructions to tree-decomposition
• Matching, Euler tours and the Chinese postman
• Optimization, approximation, and complexity classes
• Planar 3DM is NP-complete
• The monadic second-order logic of graphs III : tree-decompositions, minors and complexity issues
• The path partition problem and related problems in bipartite graphs
• Treewidth. Computations and approximations

Cited in

(10)

• A \(\frac{3}{2}\) approximation for a constrained forest problem
• Finding compact scheme forests in nested normal form is NP-hard
• Heuristic approaches for the optimal wiring in large scale robotic skin design
• Algorithms and Data Structures
• Navigating Forest Straight-Line Programs in Constant Time
• scientific article; zbMATH DE number 1935512 (Why is no real title available?)
• Covering a graph with a constrained forest (extended abstract)
• A class of heuristics for the constrained forest problem
• A 3/2-approximation algorithm for some minimum-cost graph problems
• scientific article; zbMATH DE number 742977 (Why is no real title available?)

This page was built for publication: Complexity and approximation of the constrained forest problem

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