On finding separators in temporal split and permutation graphs

DOI10.1007/978-3-030-86593-1_27OpenAlexW3202888266MaRDI QIDQ5918685

Rolf Niedermeier, Malte Renken, Hendrik Molter, Nicolas Maack

Publication date: 20 May 2022

Published in: Fundamentals of Computation Theory (Search for Journal in Brave)

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

zbMATH Keywords

NP-hardnessfixed-parameter tractabilityspecial graph classesconnectivity problemstemporal graphs

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Related Items (3)

Temporal interval cliques and independent sets ⋮ On finding separators in temporal split and permutation graphs ⋮ The complexity of finding temporal separators under waiting time constraints

Cites Work

• Unnamed Item
• Unnamed Item
• On a graph partition problem with application to VLSI layout
• Algorithmic graph theory and perfect graphs
• The complexity of finding small separators in temporal graphs
• Assigning times to minimise reachability in temporal graphs
• On temporal graph exploration
• Deleting edges to restrict the size of an epidemic in temporal networks
• Graph Classes: A Survey
• Treewidth and Pathwidth of Permutation Graphs
• Parameterized and Exact Computation
• Temporal Network Optimization Subject to Connectivity Constraints
• Permutation Graphs and Transitive Graphs
• COMPUTING SHORTEST, FASTEST, AND FOREMOST JOURNEYS IN DYNAMIC NETWORKS
• A NEW MEASURE OF RANK CORRELATION
• Connectivity and inference problems for temporal networks
• Temporal graph classes: a view through temporal separators

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