On exploring always-connected temporal graphs of small pathwidth
Publication date
2019-02
Authors
Bodlaender, H.L.
van der Zanden, Tom C.
Editors
Advisors
Supervisors
Document Type
Article
Metadata
Show full item recordCollections
License
taverne
Abstract
We show that the TEMPORAL GRAPH EXPLORATION PROBLEM is NP-complete, even when the underlying graph has pathwidth 2 and at each time step, the current graph is connected.
Keywords
Computational complexity, Graph algorithms, Graph exploration, Pathwidth, Temporal graphs, Taverne, Theoretical Computer Science, Signal Processing, Information Systems, Computer Science Applications
Citation
Bodlaender, H L & van der Zanden, T C 2019, 'On exploring always-connected temporal graphs of small pathwidth', Information Processing Letters, vol. 142, pp. 68-71. https://doi.org/10.1016/j.ipl.2018.10.016