| 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 |
|