The complexity of finding small separators in temporal graphs

DOI10.1016/j.jcss.2019.07.006zbMath1436.68265OpenAlexW2968468046WikidataQ127392267 ScholiaQ127392267MaRDI QIDQ2009634

Till Fluschnik, Philipp Zschoche, Hendrik Molter, Rolf Niedermeier

Publication date: 29 November 2019

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

Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2018/9627/

zbMATH Keywords

parameterized complexitylength-bounded cuts(non-)strict temporal pathsnode multiway cutsingle-source shortest paths problemsingle-source shortest strict temporal pathtemporal core

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Parameterized complexity, tractability and kernelization (68Q27)

Related Items (32)

As Time Goes By: Reflections on Treewidth for Temporal Graphs ⋮ Mengerian temporal graphs revisited ⋮ Maximum 0-1 timed matching on temporal graphs ⋮ Deleting edges to restrict the size of an epidemic in temporal networks ⋮ Optimizing reachability sets in temporal graphs by delaying ⋮ Towards classifying the polynomial-time solvability of temporal betweenness centrality ⋮ Mengerian graphs: characterization and recognition ⋮ Towards Classifying the Polynomial-Time Solvability of Temporal Betweenness Centrality ⋮ Multistage \(s-t\) path: confronting similarity with dissimilarity ⋮ The complexity of growing a graph ⋮ Disentangling the computational complexity of network untangling ⋮ Untangling temporal graphs of bounded degree ⋮ Computing maximum matchings in temporal graphs ⋮ Timeline cover in temporal graphs: exact and approximation algorithms ⋮ On computing large temporal (unilateral) connected components ⋮ Parameterised temporal exploration problems ⋮ On short fastest paths in temporal graphs ⋮ Finding temporal paths under waiting time constraints ⋮ The Complexity of Finding Small Separators in Temporal Graphs ⋮ Exploration of \(k\)-edge-deficient temporal graphs ⋮ Finding Temporal Paths Under Waiting Time Constraints. ⋮ Multistage s-t Path: Confronting Similarity with Dissimilarity in Temporal Graphs ⋮ Exploration of \(k\)-edge-deficient temporal graphs ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Sliding window temporal graph coloring ⋮ Feedback edge sets in temporal graphs ⋮ On finding separators in temporal split and permutation graphs ⋮ On finding separators in temporal split and permutation graphs ⋮ A faster parameterized algorithm for temporal matching ⋮ The complexity of finding temporal separators under waiting time constraints ⋮ Finding colorful paths in temporal graphs

Uses Software

• cliques

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Traveling salesman problems in temporal graphs
• Fundamentals of parameterized complexity
• Paths of bounded length and their cuts: parameterized complexity and algorithms
• Interdiction problems on planar graphs
• Computing maximal cliques in link streams
• Most vital links and nodes in weighted networks
• Mengerian theorems for paths of bounded length
• The complexity of optimal design of temporally connected graphs
• Temporal flows in temporal networks
• Parametrized complexity theory.
• On temporal graph exploration
• On Multiway Cut Parameterized above Lower Bounds
• Length-bounded cuts and flows
• Maximal Flow Through a Network
• Easy problems for tree-decomposable graphs
• On the Size and the Approximability of Minimum Temporally Connected Subgraphs
• Fractals for Kernelization Lower Bounds
• Temporal Vertex Cover with a Sliding Time Window
• The Complexity of Finding Small Separators in Temporal Graphs
• Cluster Editing in Multi-Layer and Temporal Graphs.
• Temporal Network Optimization Subject to Connectivity Constraints
• Parameterized Algorithms
• An Introduction to Temporal Graphs: An Algorithmic Perspective^*
• Connectivity and inference problems for temporal networks

This page was built for publication: The complexity of finding small separators in temporal graphs