Approximation Algorithms for NP-Complete Problems on Planar Graphs (Preliminary Version)
Brenda S. BakerPublished in: FOCS (1983)
Keyphrases
- preliminary version
- np complete problems
- approximation algorithms
- max cut
- planar graphs
- np complete
- vertex cover
- np hard
- graph coloring
- undirected graph
- phase transition
- special case
- worst case
- hard problems
- minimum cost
- satisfiability problem
- sat problem
- scheduling problem
- randomly generated
- optimal solution
- integer programming
- constraint satisfaction problems
- linear program
- combinatorial problems
- job shop scheduling
- computational complexity
- lower bound
- evolutionary algorithm
- optimization problems
- linear programming
- primal dual
- constraint satisfaction
- probabilistic inference