The complexity of finding temporal separators under waiting time constraints
type: Item
instance of: scholarly article
title: The complexity of finding temporal separators under waiting time constraints
author: Hendrik Molter
published in: Information Processing Letters
publication date: 2021-12-14T00:00:00Z
full work available at URL: https://arxiv.org/abs/2107.01609
Mathematics Subject Classification ID: 68Qxx
zbMATH DE Number: 7444836
zbMATH Keywords: temporal graphs
zbMATH Keywords: computational complexity
zbMATH Keywords: \(\Sigma_2^{\mathrm{P}}\)-completeness
zbMATH Keywords: parameterized complexity
zbMATH Keywords: restless temporal paths
MaRDI profile type: Publication
OpenAlex ID: W3216381664
cites work: Q3056948
cites work: Computational Complexity
cites work: Q3452868
cites work: Q5689807
cites work: Finding temporal paths under waiting time constraints
cites work: Parameterized Algorithms
cites work: Q4503944
cites work: Fundamentals of parameterized complexity
cites work: Parametrized complexity theory.
cites work: Temporal graph classes: a view through temporal separators
cites work: Parameterized complexity classes beyond para-NP
cites work: Temporal Network Theory
cites work: Connectivity and inference problems for temporal networks
cites work: Enumerating maximal cliques in link streams with durations
cites work: On finding separators in temporal split and permutation graphs
cites work: An Introduction to Temporal Graphs: An Algorithmic Perspective*
cites work: Networks
cites work: Q5710169
cites work: Non deterministic polynomial optimization problems and their approximations
cites work: The polynomial-time hierarchy
cites work: The complexity of finding small separators in temporal graphs
DOI: 10.1016/J.IPL.2021.106229
Recommended article: The Complexity of Finding Small Separators in Temporal Graphs
Recommended article: The complexity of finding small separators in temporal graphs
Recommended article: The complexity of temporal constraint satisfaction problems
Recommended article: On finding separators in temporal split and permutation graphs
Recommended article: On Restricted Disjunctive Temporal Problems: Faster Algorithms and Tractability Frontier
Recommended article: Finding Temporal Paths Under Waiting Time Constraints.
Recommended article: Finding temporal paths under waiting time constraints
Recommended article: Q5750422
Recommended article: Q5094139
description: scientific article; zbMATH DE number 7444836