On exploring temporal graphs of small pathwidth

Hans L. Bodlaender, Tom C. van der Zanden

Research output: Contribution to journalArticleAcademic

17 Downloads (Pure)

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.
Original languageEnglish
Article number1807.11869
Number of pages7
JournalarXiv
Volume2018
Publication statusPublished - 31 Jul 2018

Fingerprint Dive into the research topics of 'On exploring temporal graphs of small pathwidth'. Together they form a unique fingerprint.

Cite this