On finding separators in temporal split and permutation graphs

DOI10.1016/J.JCSS.2023.01.004MaRDI QIDQ5925700zbMATH OpenOpenAlexFDO

Authors Nicolas Maack, Hendrik Molter, Rolf Niedermeier, Malte Renken

Publication date 21 April 2023

Published in Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.jcss.2023.01.004

zbMATH Keywords

fixed-parameter tractabilityNP-hardnessspecial graph classesconnectivity problemstemporal graphs

Mathematics Subject Classification ID

Computer science (68-XX)

Cites work

• scientific article; zbMATH DE number 3910422 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 2234775 (Why is no real title available?)
• A NEW MEASURE OF RANK CORRELATION
• A faster parameterized algorithm for temporal matching
• Algorithmic graph theory and perfect graphs
• As Time Goes By: Reflections on Treewidth for Temporal Graphs
• Assigning times to minimise reachability in temporal graphs
• COMPUTING SHORTEST, FASTEST, AND FOREMOST JOURNEYS IN DYNAMIC NETWORKS
• Connectivity and inference problems for temporal networks
• Deleting edges to restrict the size of an epidemic in temporal networks
• Edge exploration of temporal graphs
• Feedback edge sets in temporal graphs
• Finding temporal paths under waiting time constraints
• Graph Classes: A Survey
• Improved upper bounds for vertex cover
• Minimal Split Completions of Graphs
• On a graph partition problem with application to VLSI layout
• On finding separators in temporal split and permutation graphs
• Parameterized and Exact Computation
• Permutation Graphs and Transitive Graphs
• Temporal network optimization subject to connectivity constraints
• The complexity of finding small separators in temporal graphs
• The complexity of finding temporal separators under waiting time constraints
• Towards classifying the polynomial-time solvability of temporal betweenness centrality
• Treewidth and Pathwidth of Permutation Graphs

Cited in

(6)

• scientific article; zbMATH DE number 7559396 (Why is no real title available?)
• Temporal reachability minimization: delaying vs. deleting
• On finding separators in temporal split and permutation graphs
• The complexity of finding temporal separators under waiting time constraints
• Disjoint temporal walks under waiting time constraints
• Counting temporal paths

This page was built for publication: On finding separators in temporal split and permutation graphs

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