Title of article
An effectivemultileveltabusearchapproachforbalancedgraphpartitioning
Author/Authors
Una Benlic، نويسنده , , Jin-KaoHao، نويسنده ,
Issue Information
ماهنامه با شماره پیاپی سال 2011
Pages
10
From page
1066
To page
1075
Abstract
Graph partitioningisoneofthefundamentalNP-completeproblemswhichiswidelyappliedinmany
domains,suchasVLSIdesign,imagesegmentation,datamining,etc.Givenagraph G¼(V,E), thebalanced
k-partitioningproblemconsistsinpartitioningthevertexset V into k disjointsubsetsofaboutthesame
size, suchthatthenumberofcuttingedgesisminimized.Inthispaper,wepresentamultilevelalgorithm
for balancedpartition,whichintegratesapowerfulrefinementprocedurebasedontabusearchwith
periodicperturbations.Experimentalevaluationsonawidecollectionofbenchmarkgraphsshowthatthe
proposedapproachnotonlycompetesveryfavorablywiththetwowell-knownpartitioningpackages
METIS andCHACO,butalsoimprovesmorethantwothirdsofthebestbalancedpartitionseverreportedin
the literature.
Keywords
Balanced partitioning , Multilevel approach , Iterated tabu search
Journal title
Computers and Operations Research
Serial Year
2011
Journal title
Computers and Operations Research
Record number
927925
Link To Document