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.
Detta förbättrades på O(m log 3 n) algoritmen i Karger REF och är den senaste tidens komplexitet för kantanslutning.
Minimum cuts in near-linear time
{'venue': 'JACM', 'journal': None, 'mag_field_of_study': ['Computer Science', 'Mathematics']}