Skip to content Skip to navigation
University of Warwick
  • Study
  • |
  • Research
  • |
  • Business
  • |
  • Alumni
  • |
  • News
  • |
  • About

University of Warwick
Publications service & WRAP

Highlight your research

  • WRAP
    • Home
    • Search WRAP
    • Browse by Warwick Author
    • Browse WRAP by Year
    • Browse WRAP by Subject
    • Browse WRAP by Department
    • Browse WRAP by Funder
    • Browse Theses by Department
  • Publications Service
    • Home
    • Search Publications Service
    • Browse by Warwick Author
    • Browse Publications service by Year
    • Browse Publications service by Subject
    • Browse Publications service by Department
    • Browse Publications service by Funder
  • Help & Advice
University of Warwick

The Library

  • Login
  • Admin

Fully dynamic approximate maximum matching and minimum vertex cover in O(log3 n) worst case update time

Tools
- Tools
+ Tools

Bhattacharya, Sayan, Henzinger, Monika and Nanongkai, Danupon (2017) Fully dynamic approximate maximum matching and minimum vertex cover in O(log3 n) worst case update time. In: Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, Barcelona, Spain, 16-19 Jan 2017. Published in: Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms pp. 470-489. ISBN 9781611974782. doi:10.1137/1.9781611974782.30

[img]
Preview
PDF
WRAP-fully-dynamic-approximate-maximum-matching-minimum-vertex-cover-Bhattacharya-2017.pdf - Published Version - Requires a PDF viewer.

Download (944Kb) | Preview
Official URL: http://dx.doi.org/10.1137/1.9781611974782.30

Request Changes to record.

Abstract

We consider the problem of maintaining an approximately maximum (fractional) matching and an approximately minimum vertex cover in a dynamic graph. Starting with the seminal paper by Onak and Rubinfeld [STOC 2010], this problem has received significant attention in recent years. There remains, however, a polynomial gap between the best known worst case update time and the best known amortised update time for this problem, even after allowing for randomisation. Specifically, Bernstein and Stein [ICALP 2015, SODA 2016] have the best known worst case update time. They present a deterministic data structure with approximation ratio (3/2 + ∊) and worst case update time O(m1/4/ ∊2), where m is the number of edges in the graph. In recent past, Gupta and Peng [FOCS 2013] gave a deterministic data structure with approximation ratio (1+ ∊) and worst case update time No known randomised data structure beats the worst case update times of these two results. In contrast, the paper by Onak and Rubinfeld [STOC 2010] gave a randomised data structure with approximation ratio O(1) and amortised update time O(log2 n), where n is the number of nodes in the graph. This was later improved by Baswana, Gupta and Sen [FOCS 2011] and Solomon [FOCS 2016], leading to a randomised date structure with approximation ratio 2 and amortised update time O(1).

We bridge the polynomial gap between the worst case and amortised update times for this problem, without using any randomisation. We present a deterministic data structure with approximation ratio (2 + ∊) and worst case update time O(log3 n), for all sufficiently small constants ∊.

Item Type: Conference Item (Paper)
Subjects: Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software
Divisions: Faculty of Science > Computer Science
Library of Congress Subject Headings (LCSH): Graph algorithms, Graph theory
Journal or Publication Title: Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms
Publisher: SIAM
ISBN: 9781611974782
Book Title: Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms
Official Date: 2017
Dates:
DateEvent
2017Published
16 January 2017Available
10 September 2017Accepted
Page Range: pp. 470-489
DOI: 10.1137/1.9781611974782.30
Status: Peer Reviewed
Publication Status: Published
Access rights to Published version: Open Access
RIOXX Funder/Project Grant:
Project/Grant IDRIOXX Funder NameFunder ID
340506Seventh Framework Programmehttp://dx.doi.org/10.13039/100011102
2015-0465Vetenskapsrådethttp://dx.doi.org/10.13039/501100004359
Conference Paper Type: Paper
Title of Event: Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms
Type of Event: Conference
Location of Event: Barcelona, Spain
Date(s) of Event: 16-19 Jan 2017

Request changes or add full text files to a record

Repository staff actions (login required)

View Item View Item

Downloads

Downloads per month over past year

View more statistics

twitter

Email us: wrap@warwick.ac.uk
Contact Details
About Us