Nyligen, ett antal forskare har undersökt en klass av graf partitionering algoritmer som minskar storleken på grafen genom att kollapsa hörn och kanter, partition den mindre grafen, och sedan uncoarsen det att konstruera en partition för den ursprungliga grafen [4, 26]. Från det tidiga arbetet var det tydligt att multilevel tekniker höll stort löfte; men det var inte känt om de kan göras för att konsekvent producera högkvalitativa partitioner för grafer som uppstår i ett brett spektrum av tillämpningsområden. Vi undersöker effektiviteten av många olika val för alla tre faser: grövre, partition av den grövsta grafen, och förfining. I synnerhet presenterar vi en ny grov heuristisk (så kallad heavydge heuristic) för vilken storleken på partitionen av den grova grafen ligger inom en liten faktor av storleken på den slutliga partitionen som erhålls efter förfining på flera nivåer. Vi presenterar också en mycket snabbare variation av Kernighan-Lin algoritmen för raffinering under uncoarsening. Vi testar vårt schema på ett stort antal grafer som uppstår inom olika områden, inklusive finita element metoder, linjär programmering, VLSI, och transport. Våra experiment visar att vårt system producerar partitioner som är konsekvent bättre än de som produceras av spektral partitionering system i betydligt mindre tid. Dessutom, när vårt system används för att beräkna fyllnad minska beställningar för glesa matriser, det producerar beställningar som har betydligt mindre fyllnad än den allmänt använda flera minimigrad algoritm.
Den slutliga partitionen, "meta-clustering", erhålls med METIS REF.
A fast and high quality multilevel scheme for partitioning irregular graphs
{'venue': 'SIAM JOURNAL ON SCIENTIFIC COMPUTING', 'journal': None, 'mag_field_of_study': ['Computer Science']}