On Directed Steiner Trees with Multiple Roots

DOI10.1007/978-3-662-53536-3_22zbMath1417.05089arXiv1604.05103OpenAlexW2341842340MaRDI QIDQ3181063

Ondřej Suchý

Publication date: 22 December 2016

Published in: Graph-Theoretic Concepts in Computer Science (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Trees (05C05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Directed graphs (digraphs), tournaments (05C20)

Related Items (3)

On Directed Steiner Trees with Multiple Roots ⋮ Clearing directed subgraphs by mobile agents. Variations on covering with paths ⋮ Tight Bounds for Planar Strongly Connected Steiner Subgraph with Fixed Number of Terminals (and Extensions)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Fundamentals of parameterized complexity
• Approximating node connectivity problems via set covers
• On the parameterized complexity of the fixed alphabet shortest common supersequence and longest common subsequence problems
• Fast polynomial-space algorithms using inclusion-exclusion. Improving on Steiner tree and related problems
• Approximation algorithms for spanner problems and directed Steiner forest
• Dynamic programming for minimum Steiner trees
• Parameterized Complexity of Directed Steiner Tree on Sparse Graphs
• Fixed-Parameter and Approximation Algorithms: A New Look
• On Directed Steiner Trees with Multiple Roots
• The Directed Steiner Network Problem is Tractable for a Constant Number of Terminals
• Fourier meets M\"{o}bius: fast subset convolution
• Send-and-Split Method for Minimum-Concave-Cost Network Flows
• The Rectilinear Steiner Tree Problem is $NP$-Complete
• Approximation Algorithms for Directed Steiner Problems
• Integrality Ratio for Group Steiner Trees and Directed Steiner Trees
• Parameterized Algorithms
• Steiner's problem in graphs and its implications
• The steiner problem in graphs
• Parameterized Complexity of Arc-Weighted Directed Steiner Problems
• On the complexity of \(k\)-SAT

This page was built for publication: On Directed Steiner Trees with Multiple Roots