Vi studerar problemet med att beräkna en minsta skärning i en enkel, oriktad graf och ger en deterministisk O(m log 2 n log log 2 n) tid algoritm. Detta förbättrar både den mest kända deterministiska körtiden för O(m log 12 n) (Kawarabayashi och Thorup [12]) och den mest kända randomiserade körtiden för O(m log 3 n) (Karger [11]) för detta problem, även om Kargers algoritm kan tillämpas ytterligare på viktade grafer. Vårt tillvägagångssätt är att använda Kawarabayashi och Thorup grafen kompression teknik, som gång på gång finner low-conductance skärningar. För att hitta dessa nedskärningar använder de en diffusion-baserad lokal algoritm. Vi använder istället en flödesbaserad lokal algoritm och anpassar deras ramverk på lämpligt sätt för att arbeta med vår flödesbaserade subrutin. Både flödes- och diffusionsbaserade metoder har en lång historia av att användas för att hitta låga ledningsnedskärningar. Diffusionsalgoritmer har flera varianter som är naturligt lokala samtidigt som det är mer komplicerat att göra flödesmetoder lokala. Vissa tidigare arbeten har visat sig vara fina egenskaper för lokala flödesbaserade algoritmer med avseende på förbättring eller rengöring av låga ledningsnedskärningar. Vår flödessubrutin är dock den första som både är lokal och ger låga ledningsnedskärningar. Det kan därför vara av oberoende intresse.
Detta förbättrades av Henzinger, Rao och Wang REF, som uppnår deterministisk körtid O(m log 2 n (log log n) 2 ).
Local Flow Partitioning for Faster Edge Connectivity
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Mathematics', 'Computer Science']}