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

DOI10.1142/S0129054118500302MaRDI QIDQ5384532zbMATH OpenOpenAlexWikidataFDO

Authors Mehdy Roayaei, Mohammadreza Razzazi

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

Graph algorithms (graph-theoretic aspects) (05C85) 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)

Recommendations

• Parameterized complexity of arc-weighted directed Steiner problems
• Parameterized complexity of arc-weighted directed Steiner problems
• The complexity landscape of fixed-parameter directed Steiner network problems
• Parameterized complexity of directed Steiner tree on sparse graphs
• Parameterized Complexity of Directed Steiner Tree on Sparse Graphs
• Parameterized Approximation Algorithms for Bidirected Steiner Network Problems
• Parameterized approximation algorithms for bidirected Steiner network problems
• An approach for the Steiner problem in directed graphs
• Approximation Algorithms for Directed Steiner Problems

Cites work

• scientific article; zbMATH DE number 1507224 (Why is no real title available?)
• scientific article; zbMATH DE number 2234775 (Why is no real title available?)
• A Theorem on Graphs, with an Application to a Problem of Traffic Control
• Fibonacci heaps and their uses in improved network optimization algorithms
• Finding the K Shortest Loopless Paths in a Network
• Improved approximation for orienting mixed graphs
• On the parameterized complexity of multiple-interval graph problems
• On the point-to-point connection problem
• Optimal orientations of graphs and digraphs: A survey
• Parameterized complexity of arc-weighted directed Steiner problems
• Routing in Point-to-Point Delivery Systems: Formulations and Solution Heuristics
• The Directed Steiner Network Problem is Tractable for a Constant Number of Terminals
• The point-to-point connection problem - analysis and algorithms

Cited in

(4)

• Parameterized complexity of arc-weighted directed Steiner problems
• Parameterized Complexity of Directed Steiner Tree on Sparse Graphs
• Parameterized complexity of directed Steiner tree on sparse graphs
• 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

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