Parameterized Complexity of Directed Steiner Network with Respect to Shared Vertices and Arcs

DOI10.1142/S0129054118500302zbMath1415.68160OpenAlexW2900751082WikidataQ128990706 ScholiaQ128990706MaRDI QIDQ5384532

Mohammadreza Razzazi, Mehdy Roayaei

Publication date: 24 June 2019

Published in: International Journal of Foundations of Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1142/s0129054118500302

zbMATH Keywords

parameterized complexityoutput-sensitive algorithmdirected Steiner networkjunction vertexshared segment

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85)

Cites Work

• Unnamed Item
• Unnamed Item
• On the parameterized complexity of reconfiguration problems
• On the point-to-point connection problem
• On the parameterized complexity of multiple-interval graph problems
• The point-to-point connection problem - analysis and algorithms
• Optimal orientations of graphs and digraphs: A survey
• Improved Approximation for Orienting Mixed Graphs
• The Directed Steiner Network Problem is Tractable for a Constant Number of Terminals
• Routing in Point-to-Point Delivery Systems: Formulations and Solution Heuristics
• Fibonacci heaps and their uses in improved network optimization algorithms
• Finding the K Shortest Loopless Paths in a Network
• A Theorem on Graphs, with an Application to a Problem of Traffic Control
• Parameterized Complexity of Arc-Weighted Directed Steiner Problems

This page was built for publication: Parameterized Complexity of Directed Steiner Network with Respect to Shared Vertices and Arcs