On the approximability of dense Steiner problems

DOI10.1016/J.JDA.2013.06.005zbMath1335.05173OpenAlexW1970092869MaRDI QIDQ396661

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

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

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A primal-dual approximation algorithm for the Steiner forest problem
• Approximating Subdense Instances of Covering Problems
• An improved LP-based approximation for steiner tree
• Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems
• Polylogarithmic inapproximability
• Improved Approximation Algorithms for PRIZE-COLLECTING STEINER TREE and TSP
• Steiner's problem in graphs and its implications
• The steiner problem in graphs

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