Abstract-Baswana, Gupta och Sen [FOCS'11] visade att fullt dynamisk maximal matchning kan upprätthållas i allmänna grafer med logaritmisk amorterad uppdateringstid. Mer specifikt, från en tom graf på fasta hörn, de utformade en randomiserad algoritm för att upprätthålla maximal matchning över alla sekvenser av kantinsättningar och raderingar med en total körtid av (logg ) i förväntan och ( log + log 2 ) med hög sannolikhet. Huruvida denna körtid kan förbättras mot ( ) har förblivit ett viktigt öppet problem. Trots betydande forskningsinsatser har denna fråga motstått många försök att lösa även för grundläggande graffamiljer som skog. I detta dokument löser vi frågan jakande, genom att presentera en randomiserad algoritm för att upprätthålla maximal matchning i allmänna grafer med konstant avskrivningarad uppdateringstid. Den optimala runtime bundet ( ) av vår algoritm håller både i förväntan och med hög sannolikhet. Som en omedelbar följd kan vi upprätthålla 2-ungefärlig vertex-täckning med konstant amorterad uppdateringstid. Detta resultat är i huvudsak det bästa man kan hoppas på (under de unika spel gissning) i samband med dynamisk ungefärlig vertex cover, kulminerar en lång rad forskning. Vår algoritm bygger på Baswana et al.'s algoritm, men är i sig annorlunda och utan tvekan enklare. Som en konsekvens av vårt förenklade tillvägagångssätt är rymdanvändningen av vår algoritm linjär i den (dynamiska) grafstorleken, medan rymdanvändningen av Baswana et al.'s algoritm är alltid minst  till ( logg ). Slutligen presenterar vi applikationer för ungefärliga viktade matchningar och distribuerade nätverk.
Solomon REF gav sedan en randomiserad maximal matchningsalgoritm med konstant amorterad tid.
Fully Dynamic Maximal Matching in Constant Update Time
{'venue': '2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS)', 'journal': '2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS)', 'mag_field_of_study': ['Computer Science', 'Mathematics']}