A complexity dichotomy for Matching Cut in (bipartite) graphs of fixed diameter.

Hoàng-Oanh Le Van Bang Le

Published in: CoRR (2018)

Keyphrases

bipartite graph
maximum matching
maximum cardinality
bipartite graph matching
maximum weight
link prediction
stable set
graph clustering
edge weights
minimum weight
computational complexity
image matching
shape matching
bipartite networks
random walk
worst case
np hard
lower bound