Complexity and approximation of the constrained forest problem

DOI10.1016/j.tcs.2010.07.018zbMath1217.68110OpenAlexW2039500680MaRDI QIDQ553340

Basile Couëtoux, Zsolt Tuza, Cristina Bazgan

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

complexityapproximationplanar graphstreewidthbipartite graphsAPX-hardnessconstrained forestptas

Mathematics Subject Classification ID

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

Related Items (2)

Heuristic approaches for the optimal wiring in large scale robotic skin design ⋮ A 3/2-approximation algorithm for some minimum-cost graph problems

Cites Work

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

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