The parameterized complexity of the minimum shared edges problem

DOI10.1016/J.JCSS.2018.12.002zbMATH Open1431.68052OpenAlexW2953737785WikidataQ127627704 ScholiaQ127627704MaRDI QIDQ2323342FDOQ2323342

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/

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

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)

Cites Work

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

Cited In (7)

• Multistage s-t Path: Confronting Similarity with Dissimilarity in Temporal Graphs
• Parameterized Complexity of Two Edge Contraction Problems with Degree Constraints
• Parameterized Complexity of Edge Interdiction Problems
• 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)