On Exploring Temporal Graphs of Small Pathwidth

Hans L. Bodlaender; Tom C. van der Zanden

On Exploring Temporal Graphs of Small Pathwidth

Hans L. Bodlaender, Tom C. van der Zanden

Research output: Contribution to journal › Article › Academic

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 language	English
Article number	1807.11869
Number of pages	7
Journal	CoRR
Publication status	Published - 2018

Keywords

Graph algorithms
Computational complexity
Temporal graphs
Graph exploration
Pathwidth

Access to Document

1807.11869Final published version, 269 KB

http://arxiv.org/abs/1807.11869

Cite this

@article{50cea869bbaf450d9d87ee267a6f08e7,

title = "On Exploring Temporal Graphs of Small Pathwidth",

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",

author = "Bodlaender, {Hans L.} and {van der Zanden}, {Tom C.}",

year = "2018",

language = "English",

journal = "CoRR",

}

TY - JOUR

T1 - On Exploring Temporal Graphs of Small Pathwidth

AU - Bodlaender, Hans L.

AU - van der Zanden, Tom C.

PY - 2018

Y1 - 2018

N2 - 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.

AB - 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.

KW - Graph algorithms

KW - Computational complexity

KW - Temporal graphs

KW - Graph exploration

KW - Pathwidth

M3 - Article

JO - CoRR

JF - CoRR

M1 - 1807.11869

ER -

On Exploring Temporal Graphs of Small Pathwidth

Abstract

Keywords

Access to Document

Fingerprint

Cite this