Issue RAIRO-Oper. Res. Volume 42, Number 4, October-December 2008 ALIO/EURO V Conference on Combinatorial Optimization Page(s) 469 - 484 DOI 10.1051/ro:2008029 Published online 04 April 2009

RAIRO-Oper. Res. 42 (2008) 469-484
DOI: 10.1051/ro:2008029

Comparison of algorithms in graph partitioning

Alain Guénoche

IML-CNRS, 163 Av. de Luminy, 13288 Marseille Cedex 9, France; guenoche@lim.univ-mrs.fr

Received December 31, 2006. Accepted January 09, 2008 Published online 4 April 2009

Abstract
We first describe four recent methods to cluster vertices of an undirected non weighted connected graph. They are all based on very different principles. The fifth is a combination of classical ideas in optimization applied to graph partitioning. We compare these methods according to their ability to recover classes initially introduced in random graphs with more edges within the classes than between them.

Mathematics Subject Classification. 05C85, 90C35, 90C59.

Key words: Graph partitioning, partition comparison, simulation.


© EDP Sciences, ROADEF, SMAI 2008

What is OpenURL?