The complexity of finding temporal separators under waiting time constraints

DOI10.1016/J.IPL.2021.106229MaRDI QIDQ2059911zbMATH OpenOpenAlexFDO

Authors 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

\(\Sigma_2^{\mathrm{P}}\)-completenesscomputational complexityparameterized complexityrestless temporal pathstemporal graphs

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Recommendations

• The complexity of finding small separators in temporal graphs
• The complexity of finding small separators in temporal graphs
• The complexity of temporal constraint satisfaction problems
• On finding separators in temporal split and permutation graphs
• On finding separators in temporal split and permutation graphs
• On restricted disjunctive temporal problems: faster algorithms and tractability frontier
• Finding Temporal Paths Under Waiting Time Constraints.
• Finding temporal paths under waiting time constraints
• scientific article; zbMATH DE number 4185056
• Tractable combinations of temporal CSPs

Cites work

• An introduction to temporal graphs: an algorithmic perspective
• Computational Complexity
• Connectivity and inference problems for temporal networks
• Enumerating maximal cliques in link streams with durations
• Finding temporal paths under waiting time constraints
• Fundamentals of parameterized complexity
• scientific article; zbMATH DE number 1507224 (Why is no real title available?)
• scientific article; zbMATH DE number 961960 (Why is no real title available?)
• scientific article; zbMATH DE number 2234775 (Why is no real title available?)
• Network flows. Theory, algorithms, and applications.
• Network science. With Márton Pósfai
• Networks
• Non deterministic polynomial optimization problems and their approximations
• On finding separators in temporal split and permutation graphs
• Parameterized algorithms
• Parameterized complexity classes beyond para-NP
• Parametrized complexity theory.
• Temporal network theory
• The complexity of finding small separators in temporal graphs
• The polynomial-time hierarchy

Cited in

(6)

• An algorithm for exact bounds on the time separation of events in concurrent systems
• On finding separators in temporal split and permutation graphs
• On finding separators in temporal split and permutation graphs
• Temporal reachability minimization: delaying vs. deleting
• Disjoint temporal walks under waiting time constraints
• Counting temporal paths

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2059911)