An efficient approach for large scale graph partitioning

Renzo Zamprogno and André R. S. Amaral ()
Additional contact information
Renzo Zamprogno: Universidade Federal do Espírito Santo
André R. S. Amaral: Universidade Federal do Espírito Santo

Journal of Combinatorial Optimization, 2007, vol. 13, issue 4, No 1, 289-320

Abstract: Abstract In this paper, we consider the problem of partitioning the set of vertices of a graph intok subsets of approximately the same cardinality in such a way that the number of edges whose endpoints are in different subsets is minimized. A greedy heuristic, called Procedure1, based on the independent growth of each subset by fronts is proposed for constructing a good-quality graph partition. In addition, we present a more sophisticated version of the greedy heuristic, called Procedure2, which periodically calls a routine to refine the partition being built. We show that the partitions generated by Procedure1 are competitive with those obtained by several constructive heuristics in the literature, e.g. spectral, geometric, as well as other greedy heuristics. Moreover, the partitions produced by Procedure2 are compared with those produced by a leading graph partitioning method in the literature.

Keywords: Graph partitioning; Greedy heuristics; Workload balancing (search for similar items in EconPapers)
Date: 2007
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10878-006-9026-4 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:13:y:2007:i:4:d:10.1007_s10878-006-9026-4

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-006-9026-4

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().