Groupe d’études et de recherche en analyse des décisions

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.