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.
Baswana m.fl. REF ger en randomiserad 2- approximation i O(log n) amorterad tid.
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']}