The complexity of finding temporal separators under waiting time constraints

DOI10.1016/j.ipl.2021.106229OpenAlexW3216381664MaRDI QIDQ2059911

Hendrik Molter

Publication date: 14 December 2021

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

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

zbMATH Keywords

computational complexityparameterized complexitytemporal graphsrestless temporal paths\(\Sigma_2^{\mathrm{P}}\)-completeness

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Related Items (1)

On finding separators in temporal split and permutation graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Fundamentals of parameterized complexity
• Non deterministic polynomial optimization problems and their approximations
• The polynomial-time hierarchy
• Enumerating maximal cliques in link streams with durations
• Finding temporal paths under waiting time constraints
• The complexity of finding small separators in temporal graphs
• Parameterized complexity classes beyond para-NP
• Parametrized complexity theory.
• Networks
• Temporal Network Theory
• Computational Complexity
• 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
• On finding separators in temporal split and permutation graphs

This page was built for publication: The complexity of finding temporal separators under waiting time constraints