Planar Multicommodity Flows, Max Cut, and the Chinese Postman Problem.

Francisco Barahona

Published in: Polyhedral Combinatorics (1990)

Keyphrases

max cut
planar graphs
graph model
min max
np complete problems
approximate inference
graph partitioning
spectral graph
search algorithm
pairwise
np hard