Vi presenterar en algoritm för att upprätthålla maximal matchning i en graf under tillägg och radering av kanter. Vår datastruktur är randomiserad som tar O(log n) förväntad amorterad tid för varje edge update där n är antalet hörn i grafen. Även om det finns en trivial O(n) algoritm för edge update, det tidigare mest kända resultatet för detta problem berodde på Ivković och Llyod [4]. För en graf med n hörn och m kanter, ger de en O (n + m) 0.7072 ) uppdatering tid algoritm som är sublinear endast för en gles graf. För det relaterade problemet med maximal matchning utformade Onak och Rubinfeld [6] en randomiserad datastruktur som uppnår O(log 2 n) förväntad avskrivningarad tid för varje uppdatering för att upprätthålla en c-ungefärlig maximal matchning för några stora konstant c. Däremot kan vi upprätthålla en faktor två ungefärlig maximal matchning i O(log n) förväntad amorterad tid per uppdatering som en direkt följd av det maximala matchningsschemat. Detta i sin tur innebär också en två ungefärliga vertex cover underhållsschema som tar O(log n) förväntad amortized tid per uppdatering.
Detta förbättrades av Baswana, Gupta och Sen REF till en randomiserad algoritm som upprätthåller en maximal matchning (och i synnerhet 2-ungefärlig MCM) i O(log n) förväntad avskrivningarad uppdateringstid.
Fully Dynamic Maximal Matching in O (log n) Update Time
{'venue': '2011 IEEE 52nd Annual Symposium on Foundations of Computer Science', 'journal': '2011 IEEE 52nd Annual Symposium on Foundations of Computer Science', 'mag_field_of_study': ['Mathematics', 'Computer Science']}