On exploring always-connected temporal graphs of small pathwidth

DOI10.1016/j.ipl.2018.10.016zbMath1469.68072arXiv1807.11869WikidataQ59567334 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 complexity; graph algorithms; pathwidth; graph exploration; temporal graphs

Mathematics Subject Classification ID

68R10: Graph theory (including graph drawing) in computer science

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

05C85: Graph algorithms (graph-theoretic aspects)

05C40: Connectivity