The Library
Deterministic fully dynamic data structures for vertex cover and matching
Tools
Tools
Tools
Bhattacharya, Sayan, Henzinger, Monika and Italiano, Giuseppe F. (2015) Deterministic fully dynamic data structures for vertex cover and matching. In: Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, San Diego, 4-6 Jan 2015. Published in: Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms pp. 785-804. ISBN 9781611973747. doi:10.1137/1.9781611973730.54
|
PDF
WRAP-deterministic-fully-dynamic-data-structures-Bhattacharya-2015.pdf - Accepted Version - Requires a PDF viewer. Download (791Kb) | Preview |
Official URL: http://dx.doi.org/10.1137/1.9781611973730.54
Abstract
We present the first deterministic data structures for maintaining approximate minimum vertex cover and maximum matching in a fully dynamic graph in time per update. In particular, for minimum vertex cover we provide deterministic data structures for maintaining a (2 + ε) approximation in O(log n/ε2) amortized time per update. For maximum matching, we show how to maintain a (3 + e) approximation in O(m1/3/ε2) amortized time per update, and a (4 + ε) approximation in O(m1/3/ε2) worst-case time per update. Our data structure for fully dynamic minimum vertex cover is essentially near-optimal and settles an open problem by Onak and Rubinfeld [13].
| Item Type: | Conference Item (Paper) | ||||
|---|---|---|---|---|---|
| Subjects: | Q Science > QA Mathematics | ||||
| Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science | ||||
| Library of Congress Subject Headings (LCSH): | Graph theory | ||||
| Journal or Publication Title: | Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms | ||||
| Publisher: | SIAM | ||||
| ISBN: | 9781611973747 | ||||
| Book Title: | Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms | ||||
| Official Date: | 2015 | ||||
| Dates: |
|
||||
| Page Range: | pp. 785-804 | ||||
| DOI: | 10.1137/1.9781611973730.54 | ||||
| Status: | Peer Reviewed | ||||
| Publication Status: | Published | ||||
| Funder: | Seventh Framework Programme (European Commission) (FP7), European Research Council (ERC), Italy. Ministero dell'istruzione, dell'università e della ricerca (MIUR) | ||||
| Grant number: | Grant Agreement no. 340506 (FP7) (ERC), Project AMANDA (MIUR) | ||||
| Conference Paper Type: | Paper | ||||
| Title of Event: | Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms | ||||
| Type of Event: | Other | ||||
| Location of Event: | San Diego | ||||
| Date(s) of Event: | 4-6 Jan 2015 |
Request changes or add full text files to a record
Repository staff actions (login required)
 |
View Item |
Downloads
Downloads per month over past year
