Steiner Problems with Limited Number of Branching Nodes

DOI10.1007/978-3-319-03578-9_26zbMath1406.68092OpenAlexW1855867726MaRDI QIDQ2868654

Cédric Bentz, Dimitri Watel, Marc-Antoine Weisser, Dominique Barith

Publication date: 17 December 2013

Published in: Structural Information and Communication Complexity (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-319-03578-9_26

zbMATH Keywords

graph algorithmSteiner treeparameterized complexity

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85) Signed and weighted graphs (05C22)

Related Items

On the terminal connection problem ⋮ Directed Steiner trees with diffusion costs ⋮ On the computational difficulty of the terminal connection problem ⋮ On undirected two‐commodity integral flow, disjoint paths and strict terminal connection problems ⋮ A multivariate analysis of the strict terminal connection problem

Cites Work

• The directed subgraph homeomorphism problem
• A fast algorithm for Steiner trees
• The Steiner cycle polytope
• Graph minors. XIII: The disjoint paths problem
• An 11/6-approximation algorithm for the network Steiner problem
• A threshold of ln n for approximating set cover
• Finding minimum-cost circulations by canceling negative cycles
• Polylogarithmic inapproximability
• Finding k Disjoint Paths in a Directed Planar Graph
• Approximating Rooted Steiner Networks
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Steiner Problems with Limited Number of Branching Nodes