Complexity and approximation of the constrained forest problem
type: Item
instance of: scholarly article
title: Complexity and approximation of the constrained forest problem
zbMATH Open document ID: 1217.68110
author: Cristina Bazgan
author: Basile Couëtoux
author: Zsolt Tuza
published in: Theoretical Computer Science
publication date: 2011-07-27T00:00:00Z
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 68Q17
Mathematics Subject Classification ID: 05C85
zbMATH DE Number: 5932524
zbMATH Keywords: complexity
zbMATH Keywords: approximation
zbMATH Keywords: APX-hardness
zbMATH Keywords: constrained forest
zbMATH Keywords: ptas
zbMATH Keywords: bipartite graphs
zbMATH Keywords: planar graphs
zbMATH Keywords: treewidth
MaRDI profile type: Publication
full work available at URL: j.tcs.2010.07.018
OpenAlex ID: W2039500680
cites work: Approximation algorithms for NP-complete problems on planar graphs
cites work: A partial k-arboretum of graphs with bounded treewidth
cites work: Complexity of approximating bounded variants of optimization problems
cites work: The monadic second-order logic of graphs III : tree-decompositions, minors and complexity issues
cites work: Planar 3DM is NP-complete
cites work: Algorithms – ESA 2005
cites work: Matching, Euler tours and the Chinese postman
cites work: Q3270978
cites work: A General Approximation Technique for Constrained Forest Problems
cites work: A greedy heuristic for a minimum-weight forest problem
cites work: Treewidth. Computations and approximations
cites work: Another greedy heuristic for the constrained forest problem
cites work: A class of heuristics for the constrained forest problem
cites work: The path partition problem and related problems in bipartite graphs
cites work: Optimization, approximation, and complexity classes
cites work: Graph minors. X: Obstructions to tree-decomposition
cites work: Q3330973
cites work: Extensions of Gallai's graph covering theorems for uniform hypergraphs
DOI: 10.1016/J.TCS.2010.07.018
Recommended article: A General Approximation Technique for Constrained Forest Problems
Recommended article: Q4763416
Recommended article: A class of heuristics for the constrained forest problem
Recommended article: A $\frac{3}{2}$ Approximation for a Constrained Forest Problem
Recommended article: Another greedy heuristic for the constrained forest problem
Recommended article: Computational Complexity of a Cost Allocation Approach to a Fixed Cost Spanning Forest Problem
Recommended article: Approximating the Spanning k-Tree Forest Problem
Recommended article: APPROXIMATING THE SPANNING k-TREE FOREST PROBLEM
Recommended article: Covering a Graph with a Constrained Forest (Extended Abstract)
Recommended article: The maximum agreement forest problem: Approximation algorithms and computational experiments
description: scientific article; zbMATH DE number 5932524