Improved Steiner tree algorithms for bounded treewidth
type: Item
instance of: scholarly article
title: Improved Steiner tree algorithms for bounded treewidth
zbMATH Open document ID: 1257.05166
author: Markus Chimani
author: Bernd Zey
author: Petra Mutzel
published in: Journal of Discrete Algorithms
publication date: 2013-01-18T00:00:00Z
Mathematics Subject Classification ID: 05C85
Mathematics Subject Classification ID: 05C05
zbMATH DE Number: 6126818
zbMATH Keywords: (prize-collecting) Steiner tree
zbMATH Keywords: \(k\)-cardinality tree
zbMATH Keywords: bounded treewidth
zbMATH Keywords: fixed parameter tractable
zbMATH Keywords: exact algorithm
MaRDI profile type: Publication
Wikidata QID: Q56977061
full work available at URL: j.jda.2012.04.016
OpenAlex ID: W2003272551
cites work: Complexity of Finding Embeddings in a k-Tree
cites work: Q5365098
cites work: Approximation schemes for Steiner forest on planar graphs and graphs of bounded treewidth
cites work: Q3003675
cites work: Polynomially solvable special cases of the Steiner problem in planar networks
cites work: Linear-time computation of optimal subgraphs of decomposable graphs
cites work: The Steiner problem with edge lengths 1 and 2
cites work: Fourier meets M\"{o}bius: fast subset convolution
cites work: Q4291429
cites work: A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
cites work: Treewidth: Structure and Algorithms
cites work: Q2934724
cites work: An O ( n log n ) approximation scheme for Steiner tree in planar graphs
cites work: Solving Connectivity Problems Parameterized by Treewidth in Single Exponential Time
cites work: Q4393480
cites work: The steiner problem in graphs
cites work: Send-and-Split Method for Minimum-Concave-Cost Network Flows
cites work: The Rectilinear Steiner Tree Problem is $NP$-Complete
cites work: The Steiner forest problem revisited
cites work: Treewidth. Computations and approximations
cites work: Q5710169
cites work: Practical Partitioning-Based Methods for the Steiner Problem
cites work: Q3128917
cites work: Q3875932
cites work: Graph minors. II. Algorithmic aspects of tree-width
cites work: Q3663321
cites work: Steiner trees, partial 2–trees, and minimum IFI networks
DBLP publication ID: journals/jda/ChimaniMZ12
DOI: 10.1016/J.JDA.2012.04.016
Recommended article: Improved Steiner Tree Algorithms for Bounded Treewidth
Recommended article: An improved algorithm for the Steiner tree problem with bounded edge-length
Recommended article: An Improved Algorithm for Steiner Trees
Recommended article: Improved Approximations for the Steiner Tree Problem
Recommended article: Q4763418
Recommended article: Q4952699
Recommended article: An improved LP-based approximation for Steiner tree
Recommended article: Q4469003
Recommended article: Tighter Bounds for Graph Steiner Tree Approximation
description: scientific article; zbMATH DE number 6126818