2010 | OriginalPaper | Chapter
A 3/2-Approximation Algorithm for Generalized Steiner Trees in Complete Graphs with Edge Lengths 1 and 2
Authors : Piotr Berman, Marek Karpinski, Alexander Zelikovsky
Published in: Algorithms and Computation
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
Given a graph with edge lengths and a set of pairs of vertices which should be connected (requirements) the Generalized Steiner Tree Problem (GSTP) asks for a minimum length subgraph that connects every requirement. For the Generalized Steiner Tree Problem restricted to complete graphs with edge lengths 1 and 2, we provide a 1.5-approximation algorithm. It is the first algorithm with the approximation ratio significantly better than 2 for a class of graphs for which GSTP is MAX SNP-hard.