Multilevel graph partitioning: an evolutionary approach

Kucupetek S., Polat F., Oguztuzun H.

JOURNAL OF THE OPERATIONAL RESEARCH SOCIETY, cilt.56, sa.5, ss.549-562, 2005 (SCI-Expanded) identifier identifier

  • Yayın Türü: Makale / Tam Makale
  • Cilt numarası: 56 Sayı: 5
  • Basım Tarihi: 2005
  • Doi Numarası: 10.1057/palgrave.jors.2601837
  • Dergi Adı: JOURNAL OF THE OPERATIONAL RESEARCH SOCIETY
  • Derginin Tarandığı İndeksler: Science Citation Index Expanded (SCI-EXPANDED), Social Sciences Citation Index (SSCI), Scopus
  • Sayfa Sayıları: ss.549-562
  • Orta Doğu Teknik Üniversitesi Adresli: Evet

Özet

The graph partitioning problem is defined as that of dividing the vertices of an undirected graph into a set of balanced parts through the removal of a set of edges, whose size is to be minimized. A number of researchers have investigated multilevel schemes, which coarsen the graph by collapsing vertices and edges, partition the smaller graph, and then uncoarsen it to construct a partitioning of the original graph. In this paper, a genetic algorithm for the coarsening phase of a multilevel scheme for graph partitioning is presented. The proposed approach has been demonstrated to improve the solution quality at the expense of running time.