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
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
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)
Cites Work
- Graph minors. X: Obstructions to tree-decomposition
- Optimization, approximation, and complexity classes
- Title not available (Why is that?)
- Matching, Euler tours and the Chinese postman
- A partial k-arboretum of graphs with bounded treewidth
- Complexity of approximating bounded variants of optimization problems
- Planar 3DM is NP-complete
- Approximation algorithms for NP-complete problems on planar graphs
- A General Approximation Technique for Constrained Forest Problems
- Treewidth. Computations and approximations
- The monadic second-order logic of graphs III : tree-decompositions, minors and complexity issues
- The path partition problem and related problems in bipartite graphs
- Extensions of Gallai's graph covering theorems for uniform hypergraphs
- Title not available (Why is that?)
- Algorithms – ESA 2005
- A greedy heuristic for a minimum-weight forest problem
- A class of heuristics for the constrained forest problem
- Another greedy heuristic for the constrained forest problem
Cited In (10)
- Title not available (Why is that?)
- A 3/2-approximation algorithm for some minimum-cost graph problems
- Algorithms and Data Structures
- Covering a graph with a constrained forest (extended abstract)
- A \(\frac{3}{2}\) approximation for a constrained forest problem
- Heuristic approaches for the optimal wiring in large scale robotic skin design
- Navigating Forest Straight-Line Programs in Constant Time
- Finding compact scheme forests in nested normal form is NP-hard
- A class of heuristics for the constrained forest problem
- Title not available (Why is that?)
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)
