Approximating max-cut under graph-MSO constraints.

Martin Koutecký Jon Lee Viswanath Nagarajan Xiangkun Shen

Published in: Oper. Res. Lett. (2018)

Keyphrases

max cut
planar graphs
graph model
graph partitioning
spectral graph
pairwise similarities
weighted graph
constraint satisfaction
connected components
graph structure
directed graph
multiscale
random walk
np complete
np complete problems
graphical models
np hard