On exploring always-connected temporal graphs of small pathwidth

Hans L. Bodlaender; Tom C. van der Zanden

doi:10.1016/j.ipl.2018.10.016

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 journal › Article › Academic › peer-review

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
Pages (from-to)	68-71
Number of pages	4
Journal	Information Processing Letters
Volume	142
DOIs	https://doi.org/10.1016/j.ipl.2018.10.016
Publication status	Published - Feb 2019

Keywords

Computational complexity
Graph algorithms
Graph exploration
Pathwidth
Temporal graphs

Access to Document

10.1016/j.ipl.2018.10.016

1-s2.0-S0020019018302102-mainFinal published version, 235 KBLicence: Taverne

Cite this

@article{30c26610187b43fb96a5342d3ed912bd,

title = "On exploring always-connected 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 = "Computational complexity, Graph algorithms, Graph exploration, Pathwidth, Temporal graphs",

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

year = "2019",

month = feb,

doi = "10.1016/j.ipl.2018.10.016",

language = "English",

volume = "142",

pages = "68--71",

journal = "Information Processing Letters",

issn = "0020-0190",

publisher = "Elsevier BV",

}

TY - JOUR

T1 - On exploring always-connected temporal graphs of small pathwidth

AU - Bodlaender, Hans L.

AU - van der Zanden, Tom C.

PY - 2019/2

Y1 - 2019/2

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 - Computational complexity

KW - Graph algorithms

KW - Graph exploration

KW - Pathwidth

KW - Temporal graphs

UR - http://www.scopus.com/inward/record.url?scp=85055626482&partnerID=8YFLogxK

U2 - 10.1016/j.ipl.2018.10.016

DO - 10.1016/j.ipl.2018.10.016

M3 - Article

AN - SCOPUS:85055626482

SN - 0020-0190

VL - 142

SP - 68

EP - 71

JO - Information Processing Letters

JF - Information Processing Letters

ER -

On exploring always-connected temporal graphs of small pathwidth

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this