Temporal Vertex Cover with a Sliding Time Window
- Submitting institution
-
The University of Liverpool
- Unit of assessment
- 11 - Computer Science and Informatics
- Output identifier
- 12193
- Type
- D - Journal article
- DOI
-
10.1016/j.jcss.2019.08.002
- Title of journal
- Journal of Computer and System Sciences
- Article number
- -
- First page
- 108
- Volume
- 107
- Issue
- -
- ISSN
- 0022-0000
- Open access status
- Compliant
- Month of publication
- August
- Year of publication
- 2019
- 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
- 2
- Proposed double-weighted
- No
- Reserve for an output with double weighting
- No
- Additional information
- A preliminary version of this paper appeared at ICALP'18. This paper initiated the study of a temporal analog of Vertex Cover, using the new concept of a sliding window. This concept inspired recent papers of Zamaraev and coauthors that are not REF-returned, such as "Sliding window temporal graph coloring" (AAAI'19) and "Computing Maximum Matchings in Temporal Graphs" (STACS'20), and works by others, such as "Computing Temporal Twins in Time Logarithmic in History Length" (Complex Networks 2020) and "A Faster Parameterized Algorithm for Temporal Matching" (arXiv'20).
- Author contribution statement
- -
- Non-English
- No
- English abstract
- -