Kernelization via sampling with applications to finding matchings and related problems in dynamic graph streams
- Submitting institution
-
The University of Birmingham
- Unit of assessment
- 11 - Computer Science and Informatics
- Output identifier
- 84878054
- Type
- E - Conference contribution
- DOI
-
10.1137/1.9781611974331.ch92
- Title of conference / published proceedings
- Proceedings of the 2016 Annual ACM-SIAM Symposium on Discrete Algorithms
- First page
- 1326
- Volume
- -
- Issue
- -
- ISSN
- 1071-9040
- Open access status
- Out of scope for open access requirements
- Month of publication
- January
- Year of publication
- 2016
- URL
-
-
- Supplementary information
-
-
- Request cross-referral to
- -
- Output has been delayed by COVID-19
- No
- COVID-19 affected output statement
- -
- Forensic science
- No
- Criminology
- No
- Interdisciplinary
- No
- Number of additional authors
-
6
- Research group(s)
-
-
- Citation count
- -
- Proposed double-weighted
- No
- Reserve for an output with double weighting
- No
- Additional information
- The paper develops a new subgraph-sampling primitive to obtain the first kernels for fundamental problems such as Maximum Matching and Vertex Cover on dynamic graph streams (edges can be both inserted and deleted). The significance of this paper is validated by acceptance to ACM-SIAM Symposium on Discrete Algorithms (SODA 2016) the leading algorithms conference in theoretical computer science. The principal outcome is the first semi-streaming algorithm for maximum matching which achieved sub-linear approximation ratio on dynamic streams. A further outcome is the first sub-linear space algorithm which gives a constant-factor estimation of the maximum matching in planar graphs.
- Author contribution statement
- -
- Non-English
- No
- English abstract
- -