The parameterized complexity of the minimum shared edges problem

DOI10.1016/J.JCSS.2018.12.002MaRDI QIDQ2323342zbMATH OpenOpenAlexWikidataFDO

Authors Till Fluschnik, Stefan Kratsch, Manuel Sorge, Rolf Niedermeier

Publication date 30 August 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/2015/5632/

zbMATH Keywords

fixed-parameter tractabilitykernelizationmultivariate complexity analysisW-hardnesstree decompositions of graphsVIP routing

Mathematics Subject Classification ID

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)

Recommendations

• The parameterized complexity of the minimum shared edges problem
• The minimum shared edges problem on grid-like graphs
• Finding paths with minimum shared edges
• Finding paths with minimum shared edges
• The minimum vulnerability problem

Cites work

• scientific article; zbMATH DE number 854567 (Why is no real title available?)
• scientific article; zbMATH DE number 2234775 (Why is no real title available?)
• Fault-tolerant broadcasting and gossiping in communication networks
• Finding paths with minimum shared edges
• Finding small separators in linear time via treewidth reduction
• Flows in Undirected Unit Capacity Networks
• Fundamentals of parameterized complexity
• Graph theory
• Kernelization Lower Bounds by Cross-Composition
• On the parameterized complexity of computing balanced partitions in graphs
• On the parameterized complexity of multiple-interval graph problems
• Parameterized algorithms
• Parameterized complexity of the k-arc Chinese postman problem
• Parametrized complexity theory.
• Reflections on multivariate algorithmics and problem parameterization
• Solving Connectivity Problems Parameterized by Treewidth in Single Exponential Time
• The complexity of routing with collision avoidance
• The minimum shared edges problem on grid-like graphs
• The minimum vulnerability problem
• The minimum vulnerability problem on specific graph classes
• The mixed Chinese postman problem parameterized by pathwidth and treedepth
• The parameterized complexity of the minimum shared edges problem
• Towards fully multivariate algorithmics: parameter ecology and the deconstruction of computational complexity
• Treewidth. Computations and approximations

Cited in

(7)

• Parameterized Complexity of Two Edge Contraction Problems with Degree Constraints
• Parameterized Complexity of Edge Interdiction Problems
• Multistage s-t Path: Confronting Similarity with Dissimilarity in Temporal Graphs
• The parameterized complexity of the minimum shared edges problem
• Multistage \(s-t\) path: confronting similarity with dissimilarity
• The minimum shared edges problem on grid-like graphs
• As Time Goes By: Reflections on Treewidth for Temporal Graphs

This page was built for publication: The parameterized complexity of the minimum shared edges problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2323342)