Parameterized Streaming: Maximal Matching and Vertex Cover
- Submitting institution
-
The University of Birmingham
- Unit of assessment
- 11 - Computer Science and Informatics
- Output identifier
- 84877807
- Type
- E - Conference contribution
- DOI
-
10.1137/1.9781611973730.82
- Title of conference / published proceedings
- Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2015)
- First page
- 1234
- Volume
- -
- Issue
- -
- ISSN
- -
- Open access status
- -
- Month of publication
- January
- Year of publication
- 2015
- 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
-
3
- Research group(s)
-
-
- Citation count
- -
- Proposed double-weighted
- No
- Reserve for an output with double weighting
- No
- Additional information
- This paper introduced the new paradigm of "parameterized streaming algorithm" by combining the two seemingly unrelated notions of streaming algorithm (which deals with BIG data) and parameterized algorithm (which deals with NP-completeness, or BIG Time). The significance of this paper is validated by its acceptance to ACM-SIAM Symposium On Discrete Algorithms (SODA 2015), the leading algorithms conference in theoretical computer science. The paper laid the foundation for interaction between the two previously disjoint sub-areas of streaming (SPACE) algorithms and parameterized (TIME) algorithms, and served as the inspiration for several new papers in this emerging area of research.
- Author contribution statement
- -
- Non-English
- No
- English abstract
- -