Vi förbättrar avsevärt kända tidsbegränsningar för att lösa det minsta skärproblemet på oriktade grafer. Vi använder en "semidualitet" mellan minimala snitt och maximala spannträdspackningar i kombination med våra tidigare utvecklade slumpmässiga provtagningsmetoder. Vi ger en randomiserad (Monte Carlo) algoritm som finner en minsta skärning i en m-kant, n-vertex graf med hög sannolikhet i O(m log 3 n) tid. Vi ger också en enklare randomiserad algoritm som hittar alla minimala nedskärningar med hög sannolikhet i O(n 2 log n) tid. Denna variant har en optimal parallellisering. Båda varianterna förbättrar den tidigare bästa tidslinjen för O(n 2 log 3 n). Andra tillämpningar av trädpackning metoden är nya, nästan snäva gränser på antalet nära-minimi skär en graf kan ha och en ny datastruktur för att representera dem på ett utrymmeseffektivt sätt.
(II) År 1996 tillhandahöll Karger REF den första algoritmen för minsta skärning som har en nästan linjär komplexitet i antalet kanter; den körs i O(m log 3 n) tid.
Minimum cuts in near-linear time
{'venue': 'JACM', 'journal': None, 'mag_field_of_study': ['Computer Science', 'Mathematics']}