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 ISSN 0097-5397.

Preview

PDF WRAP-deterministic-fully-dynamic-data-structures-vertex-cover-Bhattacharya-2018.pdf - Accepted Version - Requires a PDF viewer. Download (1221Kb) | Preview

Request Changes to record.

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, Engineering and Medicine > 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 Event 2018 Published 28 March 2018 Accepted
Volume:	47
Number:	3
Page Range:	pp. 859-887
DOI:	10.1137/140998925
Status:	Peer Reviewed
Publication Status:	Published
Reuse Statement (publisher, data, author rights):	“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
Date of first compliant deposit:	19 November 2019
Date of first compliant Open Access:	19 November 2019
RIOXX Funder/Project Grant:	Project/Grant ID RIOXX Funder Name Funder ID 340506 Seventh Framework Programme http://dx.doi.org/10.13039/100011102 317532 Seventh Framework Programme http://dx.doi.org/10.13039/100011102 AMANDA Ministero dell’Istruzione, dell’Università e della Ricerca http://dx.doi.org/10.13039/501100003407
Open Access Version:	ArXiv

Request changes or add full text files to a record

Repository staff actions (login required)

View Item

Downloads