Approximation Algorithms for Some Graph Partitioning Problems.

George He Jiping Liu Cheng Zhao

Published in: J. Graph Algorithms Appl. (2000)

Keyphrases

approximation algorithms
graph partitioning
vertex cover
randomized algorithms
np hard
special case
np complete
worst case
weighted graph
partitioning algorithm
primal dual
minimum cost
graph model
image segmentation
lower bound
normalized cut
approximation ratio
data clustering
input image