Issue |
RAIRO-Oper. Res.
Volume 42, Number 4, October-December 2008
ALIO/EURO V Conference on Combinatorial Optimization
|
|
---|---|---|
Page(s) | 469 - 484 | |
DOI | https://doi.org/10.1051/ro:2008029 | |
Published online | 04 April 2009 |
Comparison of algorithms in graph partitioning
IML-CNRS, 163 Av. de Luminy, 13288 Marseille Cedex 9, France; guenoche@lim.univ-mrs.fr
Received:
31
December
2006
Accepted:
9
January
2008
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
Current usage metrics show cumulative count of Article Views (full-text article views including HTML views, PDF and ePub downloads, according to the available data) and Abstracts Views on Vision4Press platform.
Data correspond to usage on the plateform after 2015. The current usage metrics is available 48-96 hours after online publication and is updated daily on week days.
Initial download of the metrics may take a while.