The complexity of finding small separators in temporal graphs
type: Item
instance of: scholarly article
title: The complexity of finding small separators in temporal graphs
zbMATH Open document ID: 1436.68265
author: Philipp Zschoche
author: Till Fluschnik
author: Hendrik Molter
author: Rolf Niedermeier
published in: Journal of Computer and System Sciences
publication date: 2019-11-29T00:00:00Z
full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2018/9627/
Mathematics Subject Classification ID: 68R10
Mathematics Subject Classification ID: 68Q17
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 68Q27
zbMATH DE Number: 7138694
zbMATH Keywords: (non-)strict temporal paths
zbMATH Keywords: temporal core
zbMATH Keywords: single-source shortest paths problem
zbMATH Keywords: single-source shortest strict temporal path
zbMATH Keywords: node multiway cut
zbMATH Keywords: length-bounded cuts
zbMATH Keywords: parameterized complexity
describes a project that uses: cliques
MaRDI profile type: Publication
OpenAlex ID: W2968468046
cites work: Q3056948
cites work: The complexity of optimal design of temporally connected graphs
cites work: Temporal Vertex Cover with a Sliding Time Window
cites work: Temporal flows in temporal networks
cites work: Easy problems for tree-decomposable graphs
cites work: On the Size and the Approximability of Minimum Temporally Connected Subgraphs
cites work: Length-bounded cuts and flows
cites work: Q5689807
cites work: Cluster Editing in Multi-Layer and Temporal Graphs.
cites work: Most vital links and nodes in weighted networks
cites work: Q3651735
cites work: Q3077955
cites work: On Multiway Cut Parameterized above Lower Bounds
cites work: Parameterized Algorithms
cites work: Fundamentals of parameterized complexity
cites work: Q5005137
cites work: On temporal graph exploration
cites work: Parametrized complexity theory.
cites work: Fractals for Kernelization Lower Bounds
cites work: Maximal Flow Through a Network
cites work: Q4198056
cites work: Paths of bounded length and their cuts: parameterized complexity and algorithms
cites work: Connectivity and inference problems for temporal networks
cites work: Mengerian theorems for paths of bounded length
cites work: Temporal Network Optimization Subject to Connectivity Constraints
cites work: An Introduction to Temporal Graphs: An Algorithmic Perspective*
cites work: Traveling salesman problems in temporal graphs
cites work: Q5710169
cites work: Interdiction problems on planar graphs
cites work: Computing maximal cliques in link streams
cites work: The Complexity of Finding Small Separators in Temporal Graphs
Wikidata QID: Q127392267
DOI: 10.1016/J.JCSS.2019.07.006
description: scientific article; zbMATH DE number 7138694