Vi presenterar en deterministisk näralinjär tidsalgoritm som beräknar kantkonnektiviteten och finner ett minsta snitt för en enkel oriktad oviktad graf G med n hörn och m kanter. Detta är den första o(mn) tid deterministiska algoritmen för problemet. I nästan linjär tid kan vi också konstruera den klassiska kaktus representation av alla minimala snitt. Den tidigare snabbast deterministiska algoritmen av Gabow från STOC'91 tog O(m + λ 2 n), där λ är kantanslutningen, men λ kunde vara  och n. Vid STOC'96 Karger presenterade en randomiserad nära linjär tid Monte Carlo algoritm för minsta skär problemet. Som han påpekar finns det inget bättre sätt att certifiera minimaliteten i den returnerade skärningen än att använda Gabows långsammare deterministiska algoritm och jämföra storlekar. Vårt huvudsakliga tekniska bidrag är en nästan linjär tidsalgoritm som kontrakterar vertex uppsättningar av en enkel ingångsgraf G med minimal grad δ, som producerar en multigraf G med O (m/δ) kanter som bevarar alla minsta skärningar av G med minst två hörn på varje sida. I vår deterministiska näralinjära tidsalgoritm, kommer vi att bryta ner problemet via low-conductance nedskärningar som hittats med PageRank a la Brin och Page (1998), som analyserats av Andersson, Chung, och Lang på FOCS'06. Normalt sådana algoritmer för low-conductance skär är randomiserade Monte Carlo algoritmer, eftersom de förlitar sig på att gissa en bra start vertex. Men i vårt fall har vi så mycket struktur att det inte behövs några gissningar.
Kawarabayashi och Thorup REF ger en deterministisk nästan linjär tidsalgoritm för det minsta skärproblemet, som körs i O(m log 12 n).
Deterministic Global Minimum Cut of a Simple Graph in Near-Linear Time
{'venue': "STOC '15", 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}