The Complexity of Finding Small Separators in Temporal Graphs
From MaRDI portal
Publication:5005147
DOI10.4230/LIPIcs.MFCS.2018.45OpenAlexW2884564598MaRDI QIDQ5005147
Till Fluschnik, Hendrik Molter, Philipp Zschoche, Rolf Niedermeier
Publication date: 4 August 2021
Full work available at URL: https://arxiv.org/abs/1711.00963
parameterized complexitylength-bounded cutssingle-source shortest paths(non-)strict temporal pathsnode multiway cuttemporal core
Related Items (4)
The complexity of finding small separators in temporal graphs ⋮ Temporal graph classes: a view through temporal separators ⋮ Unnamed Item ⋮ Temporal Cliques Admit Sparse Spanners
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Traveling salesman problems in temporal graphs
- 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
- Enumerating maximal cliques in link streams with durations
- The complexity of finding small separators in temporal graphs
- Temporal flows in temporal networks
- Parametrized complexity theory.
- On temporal graph exploration
- On Temporally Connected Graphs of Small Cost
- 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
- Efficient Minimum Cost Matching and Transportation Using the Quadrangle Inequality
- Temporal Network Optimization Subject to Connectivity Constraints
- An Introduction to Temporal Graphs: An Algorithmic Perspective*
- Connectivity and inference problems for temporal networks
- Temporal graph classes: a view through temporal separators
This page was built for publication: The Complexity of Finding Small Separators in Temporal Graphs
