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

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

[img]
Preview
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

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: 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:
DateEvent
2015Published
Page Range: pp. 785-804
DOI: 10.1137/1.9781611973730.54
Status: Peer Reviewed
Publication Status: Published
Date of first compliant deposit: 26 September 2017
Date of first compliant Open Access: 27 September 2017
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 View Item

Downloads

Downloads per month over past year

View more statistics

twitter

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