On the hardness of full Steiner tree problems

DOI10.1016/j.jda.2015.05.013zbMath1336.05054OpenAlexW974563791MaRDI QIDQ491161

Ahmad Biniaz, Anil Maheshwari, Michiel H. M. Smid

Publication date: 24 August 2015

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

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

zbMATH Keywords

bottleneck full Steiner treefull Steiner tree

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Trees (05C05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Signed and weighted graphs (05C22)

Related Items (2)

Locating service and charging stations ⋮ A multivariate analysis of the strict terminal connection problem

Cites Work

• Unnamed Item
• Unnamed Item
• An optimal algorithm for the Euclidean bottleneck full Steiner tree problem
• The relation of connected set cover and group Steiner tree
• Approximating fault-tolerant group-Steiner problems
• Node-weighted Steiner tree approximation in unit disk graphs
• A note on the terminal Steiner tree problem
• On approximation algorithms for the terminal Steiner tree problem
• On the terminal Steiner tree problem.
• Improved methods for approximating node weighted Steiner trees and connected dominating sets.
• The Euclidean bottleneck full Steiner tree problem
• Algorithms for terminal Steiner trees
• On the Full and Bottleneck Full Steiner Tree Problems
• A threshold of ln n for approximating set cover
• Polylogarithmic inapproximability
• A Polylogarithmic Approximation Algorithm for the Group Steiner Tree Problem
• A Nearly Best-Possible Approximation Algorithm for Node-Weighted Steiner Trees
• Approximation Algorithms for Directed Steiner Problems
• Node-Weighted Steiner Tree and Group Steiner Tree in Planar Graphs
• Connected Set Cover Problem and Its Applications
• Online Node-Weighted Steiner Tree and Related Problems
• A tight bound on approximating arbitrary metrics by tree metrics

This page was built for publication: On the hardness of full Steiner tree problems