PREPRINT 11/2002

Sergey S. FEDIN and Alexander S. KULIKOV

A $2^{|E|/4}$-TIME ALGORITHM FOR MAX-CUT

This preprint was accepted June 10, 2002
Contact: S. Fedin and A. Kulikov

ABSTRACT:

In this paper we present an exact algorithm solving MAX-CUT in time $\poly(|E|)\cdot 2^{|E|/4}$,
where $|E|$ is the number of edges (there can be multiple edges between two vertices). This bound improves the previously known
bound $\poly(|E|)\cdot 2^{|E|/3}$ of \cite{GHNR00}.


[Full text: (.ps.gz)]
Back to all preprints
Back to the Steklov Institute of Mathematics at St.Petersburg