Parallel approximation schemes for a class of planar and near planar combinatorial optimization problems.
type: Item
instance of: scholarly article
title: Parallel approximation schemes for a class of planar and near planar combinatorial optimization problems.
zbMATH Open document ID: 1175.90331
author: H. B. III Hunt
author: Madhav V. Marathe
author: V. Radhakrishnan
author: S. S. Ravi
author: Daniel J. Rosenkrantz
author: R. E. Stearns
published in: Information and Computation
publication date: 2003-01-14T00:00:00Z
Mathematics Subject Classification ID: 90C27
Mathematics Subject Classification ID: 05C90
zbMATH DE Number: 1853239
MaRDI profile type: Publication
full work available at URL: inco.2002.2903
OpenAlex ID: W2026992281
cites work: Easy problems for tree-decomposable graphs
cites work: Q4250161
cites work: Q4234075
cites work: Proof verification and the hardness of approximation problems
cites work: Q4527016
cites work: Approximation algorithms for NP-complete problems on planar graphs
cites work: Integer programming as a framework for optimization and approximability
cites work: Simulating (log c n )-wise independence in NC
cites work: Q4281458
cites work: A dichotomy theorem for maximum generalized satisfiability problems.
cites work: Parallel approximation schemes for problems on planar graphs
cites work: Q4886099
cites work: Q4198056
cites work: Q3757929
cites work: Q4400848
cites work: Approximation schemes for covering and packing problems in image processing and VLSI
cites work: Q4470517
cites work: NC-Approximation Schemes for NP- and PSPACE-Hard Problems for Geometric Graphs
cites work: Approximability of maximum splitting of k-sets and some other Apx-complete problems
cites work: Q4228486
cites work: On Syntactic versus Computational Views of Approximability
cites work: Q4526965
cites work: The Minimum Satisfiability Problem
cites work: Logical definability of NP optimization problems
cites work: Planar Formulae and Their Uses
cites work: Applications of a Planar Separator Theorem
cites work: Q4276003
cites work: On the hardness of approximating minimization problems
cites work: On approximation algorithms for the minimum satisfiability problem
cites work: Planar graphs: Theory and algorithms
cites work: Optimization, approximation, and complexity classes
cites work: Efficient algorithms for \(\delta\)-near-planar graph and algebraic problems
cites work: Q4527015
cites work: Graph minors. II. Algorithmic aspects of tree-width
cites work: The complexity of satisfiability problems
cites work: Q4168506
cites work: The graph genus problem is NP-complete
cites work: Positive linear programming, parallel approximation and PCP's
cites work: An approximation scheme for some Steiner tree problems in the plane
cites work: Q3907580
cites work: On Unapproximable Versions of $NP$-Complete Problems
DOI: 10.1006/INCO.2002.2903
description: scientific article; zbMATH DE number 1853239