Parallel approximation schemes for problems on planar graphs

DOI10.1007/s002360050049zbMath0858.68062OpenAlexW2091515017MaRDI QIDQ1924999

Jacobo Toran, Maria J. Serna, Josep Diaz

Publication date: 25 March 1997

Published in: Acta Informatica (Search for Journal in Brave)

Full work available at URL: http://hdl.handle.net/2117/97222

zbMATH Keywords

NC approximations schemestree contraction techniques

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items

Approximation algorithms for classes of graphs excluding single-crossing graphs as minors ⋮ Fast balanced partitioning is hard even on grids and trees ⋮ Balanced tree partition problems with virtual nodes ⋮ An \(O(n^4)\) time algorithm to compute the bisection width of solid grid graphs ⋮ Restricted Cuts for Bisections in Solid Grids: A Proof via Polygons ⋮ Parallel approximation schemes for a class of planar and near planar combinatorial optimization problems. ⋮ Fast approximation schemes for K3, 3-minor-free or K5-minor-free graphs ⋮ Balanced partitions of trees and applications

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Approximating linear programming is log-space complete for P
• Parallel approximation schemes for subset sum and knapsack problems
• A parallel algorithm for approximating the minimum cycle cover
• Planar graphs: Theory and algorithms
• Planar Depth-First Search in $O(\log n)$ Parallel Time
• Computing connected components on parallel computers
• Partitioning Planar Graphs
• Parallel Complexity of the Connected Subgraph Problem
• Approximation algorithms for NP-complete problems on planar graphs
• A simple parallel tree contraction algorithm
• A parallel approximation algorithm for positive linear programming