The Library
Deterministic fully dynamic data structures for vertex cover and matching
Tools
Tools
Tools
Bhattacharya, Sayan, Henzinger, Monika and Italiano, Giuseppe F. (2018) Deterministic fully dynamic data structures for vertex cover and matching. SIAM Journal on Computing, 47 (3). pp. 859-887. doi:10.1137/140998925
|
PDF
WRAP-deterministic-fully-dynamic-data-structures-vertex-cover-Bhattacharya-2018.pdf - Accepted Version - Requires a PDF viewer. Download (1221Kb) | Preview |
Official URL: http://dx.doi.org/10.1137/140998925
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: | Journal Article | ||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Subjects: | Q Science > QA Mathematics | ||||||||||||
| Divisions: | Faculty of Science > Computer Science | ||||||||||||
| Library of Congress Subject Headings (LCSH): | Vertex operator algebras, Algorithms, Data structures (Computer science) -- Mathematical models | ||||||||||||
| Journal or Publication Title: | SIAM Journal on Computing | ||||||||||||
| Publisher: | Society for Industrial and Applied Mathematics | ||||||||||||
| ISSN: | 0097-5397 | ||||||||||||
| Official Date: | 2018 | ||||||||||||
| Dates: |
|
||||||||||||
| Date of first compliant deposit: | 19 November 2019 | ||||||||||||
| Volume: | 47 | ||||||||||||
| Number: | 3 | ||||||||||||
| Page Range: | pp. 859-887 | ||||||||||||
| DOI: | 10.1137/140998925 | ||||||||||||
| Status: | Peer Reviewed | ||||||||||||
| Publication Status: | Published | ||||||||||||
| Publisher Statement: | “First Published in SIAM Journal on Computing in 47(3) 2018 published by the Society for Industrial and Applied Mathematics (SIAM)” “Copyright © by SIAM. Unauthorized reproduction of this article is prohibited.”) | ||||||||||||
| Access rights to Published version: | Restricted or Subscription Access | ||||||||||||
| RIOXX Funder/Project Grant: |
|
||||||||||||
| Open Access Version: |
Request changes or add full text files to a record
Repository staff actions (login required)
 |
View Item |
Downloads
Downloads per month over past year
