On the approximability of dense Steiner problems

DOI10.1016/J.JDA.2013.06.005MaRDI QIDQ396661zbMATH OpenOpenAlexFDO

Authors Mathias Hauptmann

Publication date 13 August 2014

Published in Journal of Discrete Algorithms (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.jda.2013.06.005

zbMATH Keywords

approximation algorithmsdense instancesforest problemsSteiner tree problems

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Recommendations

• scientific article; zbMATH DE number 4049088
• scientific article; zbMATH DE number 1834686
• Approximation Algorithms for Directed Steiner Problems
• scientific article; zbMATH DE number 1303557
• On the complexity of the Steiner problem
• Approximations for the Steiner multicycle problem
• On the approximability of the Steiner tree problem.
• scientific article; zbMATH DE number 1305435
• Approximation algorithms for the covering Steiner problem
• A faster approximation algorithm for the Steiner problem in graphs

Cites work

• scientific article; zbMATH DE number 2089220 (Why is no real title available?)
• scientific article; zbMATH DE number 1303564 (Why is no real title available?)
• scientific article; zbMATH DE number 1163714 (Why is no real title available?)
• scientific article; zbMATH DE number 742977 (Why is no real title available?)
• scientific article; zbMATH DE number 1445374 (Why is no real title available?)
• scientific article; zbMATH DE number 1445376 (Why is no real title available?)
• A primal-dual approximation algorithm for the Steiner forest problem
• An improved LP-based approximation for Steiner tree
• Approximating subdense instances of covering problems
• Improved Approximation Algorithms for PRIZE-COLLECTING STEINER TREE and TSP
• Polylogarithmic inapproximability
• Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems
• Steiner's problem in graphs and its implications
• The steiner problem in graphs

Cited in

(1)

• Dual heuristics on the exact solution of large Steiner problems

This page was built for publication: On the approximability of dense Steiner problems

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