Connected max cut is polynomial for graphs without $K_5\backslash e$ as a minor.

Brahim Chaourar

Published in: CoRR (2019)

Keyphrases

max cut
graph model
planar graphs
np hard
graph partitioning
np complete problems
spectral graph
data clustering
min max
multiscale
optimal solution
lower bound
point sets