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

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
Divisions:	Faculty of Science > Computer Science
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
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
Open Access Version:	ArXiv

Request changes or add full text files to a record

Repository staff actions (login required)

View Item

Downloads