On exploring always-connected temporal graphs of small pathwidth

Hans L. Bodlaender*, Tom C. van der Zanden

*Corresponding author for this work

Research output: Contribution to journalArticleAcademicpeer-review

41 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. (C) 2018 Elsevier B.V. All rights reserved.
Original languageEnglish
Pages (from-to)68-71
Number of pages4
JournalInformation Processing Letters
Volume142
DOIs
Publication statusPublished - Feb 2019

Keywords

  • Graph algorithms
  • Computational complexity
  • Temporal graphs
  • Graph exploration
  • Pathwidth

Cite this