Approximating Max-Cut under Graph-MSO Constraints.

Martin Koutecký Jon Lee Viswanath Nagarajan Xiangkun Shen

Published in: CoRR (2018)

Keyphrases

max cut
planar graphs
graph model
graph partitioning
spectral graph
random walk
constraint satisfaction
directed graph
bipartite graph
graph structure
weighted graph
linear constraints
special case
clustering algorithm
undirected graph
min max
pairwise similarities
np hard
np complete problems