I detta papper anser vi det välstuderade problemet att hitta en perfekt matchning i en d-regelbunden bipartit graf på 2n noder med m = nd kanter. Den mest kända algoritmen för allmänna bipartit grafer (på grund av Hopcroft och Karp) tar tid O(m ε n). I vanliga bipartitdiagram är dock en matchning känd för att vara beräkningsbar i O(m) tid (på grund av Cole, Ost och Schirra). I ett nyligen utfört arbete av Goel, Kapralov, och Khanna den O(m) tid bundna förbättrades först tõ O min{m, n 2.5 /d} och sedan till Õ min{m, n 2 /d}. I detta papper ger vi en randomiserad algoritm som hittar en perfekt matchning i en d-regelbunden graf och körs i O (n log n) tid (både i förväntan och med hög sannolikhet). Algoritmen utför en lämpligt trunkerad alternerande slumpmässig gång för att successivt hitta förstärkningsvägar. Vår algoritm kan ses som att använda adaptiv enhetlig provtagning, och kan därmed kringgå begränsningarna i (icke adaptiv) enhetlig provtagning som fastställts i tidigare arbete. Våra tekniker ger också en algoritm som successivt hittar en matchning i stödet för en dubbel stokastisk matris i förväntad tid O(n log 2 n), med O(m) förbehandlingstid; detta ger en enkel O (m+mn log 2 n) tid algoritm för att hitta Birkhoff-von Neumann nedbrytning av en dubbel stokastisk matris. Vi visar att randomisering är avgörande för att erhålla o(nd) tidsalgoritmer genom att etablera en (nd) lägre gräns för deterministiska algoritmer. Vi visar också att det inte finns en randomiserad algoritm som hittar en matchning i en vanlig bipartite multigraph och tar o(n log n) tid med hög sannolikhet.
Samma författare använder också en adaptiv provtagningsteknik för att ytterligare minska körtiden för att hitta en perfekt matchning i en vanlig bipartit graf till O(n log n) REF.
Perfect matchings in o(n log n) time in regular bipartite graphs
{'venue': "STOC '10", 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}