Fully dynamic maximal matching in O(log N) update time

Show simple item record

dc.contributor.author Baswana, Surender
dc.contributor.author Gupta, Manoj
dc.contributor.author Sen, Sandeep
dc.date.accessioned 2018-05-15T10:39:50Z
dc.date.available 2018-05-15T10:39:50Z
dc.date.issued 2018-01
dc.identifier.citation Baswana, Surender; Gupta, Manoj and Sen, Sandeep, "Fully dynamic maximal matching in O(log N) update time", SIAM Journal on Computing, DOI: 10.1137/16M1106158, vol. 47, no. 3, pp. 617-650, Jan. 2018. en_US
dc.identifier.isbn 1095-7111
dc.identifier.issn 0097-5397
dc.identifier.uri http://dx.doi.org/10.1137/16M1106158
dc.identifier.uri https://repository.iitgn.ac.in/handle/123456789/3655
dc.description.abstract We present an algorithm for maintaining a maximal matching in a graph under addition and deletion of edges. Our algorithm is randomized and it takes expected amortized O(log n) time for each edge update, where n is the number of vertices in the graph. Moreover, for any sequence of t edge updates, the total time taken by the algorithm is O(tlog n + n log2 n) with high probability
dc.description.statementofresponsibility by Surender Baswana, Manoj Gupta and Sandeep Sen
dc.format.extent vol. 47, no. 3, pp. 617-650
dc.language.iso en en_US
dc.publisher Society for Industrial and Applied Mathematics en_US
dc.subject matching en_US
dc.subject dynamic en_US
dc.subject graph en_US
dc.subject algorithm en_US
dc.title Fully dynamic maximal matching in O(log N) update time en_US
dc.type Article en_US
dc.relation.journal Living Reviews in Relativity

Files in this item

Files Size Format View

There are no files associated with this item.

This item appears in the following Collection(s)

Show simple item record

Search Digital Repository


My Account