Complexity and approximation of the constrained forest problem

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

Zsolt Tuza, Cristina Bazgan, Basile Couëtoux

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

complexity; approximation; planar graphs; treewidth; bipartite graphs; APX-hardness; constrained forest; ptas

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

05C85: Graph algorithms (graph-theoretic aspects)

Related Items

Heuristic approaches for the optimal wiring in large scale robotic skin design

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