A simple MAX-CUT algorithm for planar graphs - Kölner UniversitätsPublikationsServer

Liers, Frauke and Pardella, Gregor (2008). A simple MAX-CUT algorithm for planar graphs. ["eprint_fieldopt_monograph_type_preprint" not defined]. Open Access

Preview

PDF
zaik2008-579.pdf
Download (210kB) | Preview

Abstract

The max-cut problem asks for partitioning the nodes V of a graph G=(V,E) into two sets (one of which might be empty), such that the sum of weights of edges joining nodes in different partitions is maximum. Whereas for general instances the max-cut problem is NP-hard, it is polynomially solvable for certain classes of graphs. For planar graphs, there exist several polynomial-time methods determining maximum cuts for arbitrary choice of edge weights. Typically, the problem is solved by computing a minimum-weight perfect matching in some associated graph. In this work, we present a new and simple algorithm for determining maximum cuts for arbitrary weighted planar graphs. Its running time can be bounded by O(|V|^(1.5)log|V|), similar to the fastest known methods. However, our transformation yields a much smaller associated graph than that of the known methods. Furthermore, it can be computed fast. As the practical running time strongly depends on the size of the associated graph, it can be expected that our algorithm is considerably faster than the methods known in the literature. More specifically, our program can determine maximum cuts in huge realistic and random planar graphs with up to 10^6 nodes.

Item Type:

Preprints, Working Papers or Reports (["eprint_fieldopt_monograph_type_preprint" not defined])

Creators: