Constant factor approximation of vertex-cuts in planar graphs.

Eyal Amir Robert Krauthgamer Satish Rao

Published in: STOC (2003)

Keyphrases

planar graphs
constant factor approximation
approximation algorithms
undirected graph
minimum weight
np hard
greedy heuristic
minimum cost
bipartite graph
special case
spanning tree
primal dual
worst case
closest string
markov random field
weighted graph
edge weights
randomized algorithm