On Exploring Temporal Graphs of Small Pathwidth
Publication date
2018
Authors
Bodlaender, H.L.
van der Zanden, Tom C.
Editors
Advisors
Supervisors
DOI
Document Type
Article
Metadata
Show full item recordCollections
License
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
Graph algorithms, Computational complexity, Temporal graphs, Graph exploration, Pathwidth
Citation
Bodlaender, H L & van der Zanden, T C 2018, 'On Exploring Temporal Graphs of Small Pathwidth', CoRR. < http://arxiv.org/abs/1807.11869 >