Parallel approximation schemes for a class of planar and near planar combinatorial optimization problems.

DOI10.1006/inco.2002.2903zbMath1175.90331OpenAlexW2026992281MaRDI QIDQ1854505

Harry B. III Hunt, Madhav V. Marathe, Richard E. Stearns, Venkatesh Radhakrishnan, Daniel J. Rosenkrantz, S. S. Ravi

Publication date: 14 January 2003

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1006/inco.2002.2903

Mathematics Subject Classification ID

Applications of graph theory (05C90) Combinatorial optimization (90C27)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A dichotomy theorem for maximum generalized satisfiability problems.
• Optimization, approximation, and complexity classes
• Planar graphs: Theory and algorithms
• Integer programming as a framework for optimization and approximability
• Logical definability of NP optimization problems
• Approximability of maximum splitting of k-sets and some other Apx-complete problems
• On approximation algorithms for the minimum satisfiability problem
• Parallel approximation schemes for problems on planar graphs
• The graph genus problem is NP-complete
• Proof verification and the hardness of approximation problems
• Easy problems for tree-decomposable graphs
• Graph minors. II. Algorithmic aspects of tree-width
• Approximation schemes for covering and packing problems in image processing and VLSI
• Applications of a Planar Separator Theorem
• Planar Formulae and Their Uses
• On Syntactic versus Computational Views of Approximability
• The Minimum Satisfiability Problem
• Approximation algorithms for NP-complete problems on planar graphs
• Simulating (log ^c n )-wise independence in NC
• On the hardness of approximating minimization problems
• An approximation scheme for some Steiner tree problems in the plane
• NC-Approximation Schemes for NP- and PSPACE-Hard Problems for Geometric Graphs
• Positive linear programming, parallel approximation and PCP's
• The complexity of satisfiability problems
• On Unapproximable Versions of $NP$-Complete Problems