On Temporal Graph Exploration
- Submitting institution
-
The University of Leicester
- Unit of assessment
- 11 - Computer Science and Informatics
- Output identifier
- 1400
- Type
- E - Conference contribution
- DOI
-
10.1007/978-3-662-47672-7_36
- Title of conference / published proceedings
- Proceedings of the 42nd International Colloquium on Automata, Languages, and Programming
- First page
- 444
- Volume
- 9134
- Issue
- -
- ISSN
- 0302-9743
- Open access status
- Out of scope for open access requirements
- Month of publication
- June
- Year of publication
- 2015
- URL
-
-
- Supplementary information
-
https://doi.org/10.1007/978-3-662-47672-7_36
- 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
-
2
- Research group(s)
-
-
- Citation count
- 22
- Proposed double-weighted
- No
- Reserve for an output with double weighting
- No
- Additional information
- This paper makes substantial contributions to the growing body of research on temporal networks. It completely closes the gap left open by previous work (Michail and Spirakis, MFCS 2014) regarding the approximability of the temporal exploration problem. It initiates the study of the problem for specific underlying graphs (including graphs with bounded treewidth and grids) and introduces a novel multi-agent to single-agent technique. Results of this highly cited paper are discussed in detail in a survey paper by Michail (Internet Mathematics 2016). The exploration of temporal rings was followed up by DiLuna et al. (ICDCS 2016) in a distributed context.
- Author contribution statement
- -
- Non-English
- No
- English abstract
- -