Parameterized complexity of arc-weighted directed Steiner problems

DOI10.1137/100794560MaRDI QIDQ5894323zbMATH OpenOpenAlexFDO

Authors Jiong Guo, Rolf Niedermeier, Ondřej Suchý

Publication date 27 October 2011

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/100794560

zbMATH Keywords

directed Steiner networkparameterized complexitySteiner subgraphSteiner tree

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Algorithms in computer science (68W99)

Recommendations

• Parameterized complexity of arc-weighted directed Steiner problems
• Parameterized Complexity of Directed Steiner Network with Respect to Shared Vertices and Arcs
• 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

Cited in

(18)

• Revising Johnson's table for the 21st century
• Augmenting weighted graphs to establish directed point-to-point connectivity
• Parameterized Complexity of Directed Steiner Tree on Sparse Graphs
• On directed Steiner trees with multiple roots
• The complexity landscape of fixed-parameter directed Steiner network problems
• Parameterized approximation algorithms for bidirected Steiner network problems
• Complexity of the Steiner Network Problem with Respect to the Number of Terminals
• Tight bounds for planar strongly connected Steiner subgraph with fixed number of terminals (and extensions)
• Parameterized complexity of directed Steiner tree on sparse graphs
• Parameterized Complexity of Directed Steiner Network with Respect to Shared Vertices and Arcs
• scientific article; zbMATH DE number 7053371 (Why is no real title available?)
• Parameterized approximation schemes for Steiner trees with small number of Steiner vertices
• Parameterized complexity of arc-weighted directed Steiner problems
• An ETH-tight algorithm for bidirected Steiner connectivity
• Subexponential parameterized directed Steiner network problems on planar graphs: a complete classification
• The complexity landscape of fixed-parameter directed Steiner network problems
• The strongish planted clique hypothesis and its consequences
• Title not available (Why is no real title available?)

This page was built for publication: Parameterized complexity of arc-weighted directed Steiner problems

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