A deterministic near-linear time algorithm for finding minimum cuts in planar graphs.

Parinya Chalermsook Jittat Fakcharoenphol Danupon Nanongkai

Published in: SODA (2004)

Keyphrases

worst case
k means
np hard
graph structure
planar graphs
optimal solution
linear programming
em algorithm
closed form
knapsack problem
upper and lower bounds