Feedback edge sets in temporal graphs

DOI10.1016/J.DAM.2021.09.029zbMath1479.05338arXiv2003.13641OpenAlexW3208823229MaRDI QIDQ5918410

Malte Renken, Roman Haag, Hendrik Molter, Rolf Niedermeier

Publication date: 7 December 2021

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

dynamic programmingNP-complete problemsfixed-parameter tractabilityMSOtemporal cyclestemporal paths

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Dynamic programming (90C39) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (1)

On finding separators in temporal split and permutation graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Sparsity. Graphs, structures, and algorithms
• The complexity of finding small separators in temporal graphs
• Temporal cliques admit sparse spanners
• The complexity of optimal design of temporally connected graphs
• Simultaneous feedback edge set: a parameterized perspective
• On Generating Triangle-Free Graphs
• Easy problems for tree-decomposable graphs
• Edge-Deletion Problems
• On the Size and the Approximability of Minimum Temporally Connected Subgraphs
• As Time Goes By: Reflections on Treewidth for Temporal Graphs
• Temporal Network Theory
• Digraphs
• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
• An Introduction to Temporal Graphs: An Algorithmic Perspective^*
• Fixed-Parameter Tractability of Multicut in Directed Acyclic Graphs
• Connectivity and inference problems for temporal networks
• Temporal graph classes: a view through temporal separators
• Feedback edge sets in temporal graphs

This page was built for publication: Feedback edge sets in temporal graphs