On exploring always-connected temporal graphs of small pathwidth

DOI10.1016/j.ipl.2018.10.016zbMath1469.68072arXiv1807.11869OpenAlexW2898312999WikidataQ59567334 ScholiaQ59567334MaRDI QIDQ1628692

Hans L. Bodlaender, Tom C. van der Zanden

Publication date: 5 December 2018

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1807.11869

zbMATH Keywords

computational complexitygraph algorithmspathwidthgraph explorationtemporal graphs

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Connectivity (05C40)

Related Items (6)

As Time Goes By: Reflections on Treewidth for Temporal Graphs ⋮ Non-strict Temporal Exploration ⋮ Parameterised temporal exploration problems ⋮ Exploration of \(k\)-edge-deficient temporal graphs ⋮ Exploration of \(k\)-edge-deficient temporal graphs ⋮ Exploration of dynamic cactuses with sub-logarithmic overhead

Cites Work

• Unnamed Item
• Traveling salesman problems in temporal graphs
• Graph minors. I. Excluding a forest
• Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth
• On temporal graph exploration
• Fast Hamiltonicity Checking Via Bases of Perfect Matchings
• Parameterized Algorithms
• An Introduction to Temporal Graphs: An Algorithmic Perspective^*
• Connectivity and inference problems for temporal networks
• Temporal graph classes: a view through temporal separators

This page was built for publication: On exploring always-connected temporal graphs of small pathwidth