Spectral Approaches to Max-cut Problematic
Dragan Stevanovic – University of Nis, Serbie
We present a new spectral upper bound for the max-cut problem and compare it to the known Poljak-Delorme eigenvalue bound. Besides, we are discussing a recent spectral characterization of bipartite graphs and use it to propose a new and simple heuristic for finding a bipartite subgraph.