Lower bounds for the relative greedy algorithm for approximating Steiner trees

DOI10.1002/net.20100zbMath1129.90057OpenAlexW3215504420MaRDI QIDQ5469129

Stefan Kirchner, Stefan Hougardy

Publication date: 16 May 2006

Published in: Networks (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1002/net.20100

zbMATH Keywords

Steiner tree problemanalysis of algorithmslower boundsgraph algorithmsapproximation algorithms

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Trees (05C05) Abstract computational complexity for mathematical programming problems (90C60) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (2)

A factoring approach for the Steiner tree problem in undirected networks ⋮ The Clustered Selected-Internal Steiner Tree Problem

This page was built for publication: Lower bounds for the relative greedy algorithm for approximating Steiner trees