###
Steklov Institute of Mathematics at St.Petersburg

#
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