Abstrakt. Den modelleringsflexibilitet som hypergrafer ger har fått stort intresse från det kombinatoriska vetenskapliga samfundet, vilket leder till nya modeller och algoritmer, deras tillämpningar och utveckling av tillhörande verktyg. Hypergrafer är nu ett standardverktyg i kombinatoriska vetenskapliga beräkningar. Modelleringen flexibilitet hypergrafer kommer dock till en kostnad: algoritmer på hypergrafer är i sig mer komplicerade än de på grafer, som ibland översätter till icke-triviala ökningar i bearbetningstider. Varken modellering flexibilitet hypergraphs, eller runtime effektivitet graf algoritmer kan förbises. Därför bör den nya forskningsinriktningen vara hur man skickligt kan göra en avvägning mellan de två. Detta arbete tar upp en metod för denna kompromiss genom att lösa problemet med partitionering av hypergrafer genom att hitta vertex-separatorer på grafer. Specifikt, vi undersöker hur man löser hypergraph partitioning problem genom att söka en vertex separator på dess nät skärningskurva (NIG), där varje nät av hypergraph representeras av en vertex, och två hörn delar en kant om deras nät har en gemensam vertex. Vi föreslår ett vertex-vägningssystem för att uppnå bra nodbalanserade hypergrafer, eftersom NIG-modellen inte kan bevara nodbalanseringsinformation. Vertex-removal och vertex-splitting tekniker beskrivs för att optimera cutnet och konnektivitetsmått, respektive, under rekursiva bidelning paradigm. Vi utvecklade också implementeringar av våra föreslagna hypergraph partitionering formuleringar genom att anta och ändra en state-of-the-art graf partitioning av vertex avskiljare verktyg onmetis. Experiment som utförs på en stor samling glesa matriser visar effektiviteten av våra föreslagna tekniker. Nyckelord. partitionering av hypergrafer; kombinatorisk vetenskaplig beräkning; grafpartitionering av vertexseparator; glesa matriser. AMS-ämnesklassificeringar. En hypergraf är en generalisering av en graf, eftersom den ersätter kanter som endast förbinder två hörn, med hyperkanter (nät) som kan ansluta flera hörn. Denna generalisering ger en kritisk modelleringsflexibilitet som möjliggör korrekt formulering av många viktiga problem i kombinatoriska vetenskapliga beräkningar. Efter deras introduktion i [7, 38], modellering kraften av hypergrafer tilltalade många forskare och de tillämpades på en mängd olika tillämpningar inom vetenskaplig databehandling [1, 4, 6, 8, 10, 11, 12, 14, 19, 29, 30, 33, 44, 45, 48, 49, 50, 51, 52, 53, 54]. Hypergrafer och hypergrafpartitionering är nu standardverktyg för kombinatorisk vetenskaplig beräkning. Den ökande populariteten för hypergrafer har åtföljts av utvecklingen av effektiva verktyg för partitionering av hypergrafer (HP): bred tillämpning av hypergrafer motiverade utveckling av snabba HP-verktyg och tillgång till effektiva HP-verktyg motiverade ytterligare tillämpningar. Denna goda cykel producerade sekventiella HP-verktyg såsom hMetiS [28], PaToH [9] och Mondriaan [52], och parallella HP-verktyg sådana
Kayaaslan m.fl. REF presenterar en heuristisk metod för hypergrafpartitionering baserad på grafpartitionering av vertexseparator (GPVS), ett förfarande som för p = 2 partitionerar hörnen i en graf i två oanslutna uppsättningar och en separatoruppsättning.
PARTITIONING HYPERGRAPHS IN SCIENTIFIC COMPUTING APPLICATIONS THROUGH VERTEX SEPARATORS ON GRAPHS
{'venue': 'SIAM J. Scientific Computing', 'journal': 'SIAM J. Scientific Computing', 'mag_field_of_study': ['Mathematics', 'Computer Science']}