Lower bounds for the relative greedy algorithm for approximating Steiner trees

DOI10.1002/NET.20100MaRDI QIDQ5469129zbMATH OpenOpenAlexFDO

Authors Stefan Hougardy, Stefan Kirchner

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

analysis of algorithmsapproximation algorithmsgraph algorithmslower boundsSteiner tree problem

Mathematics Subject Classification ID

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

Recommendations

• scientific article; zbMATH DE number 2044939
• scientific article; zbMATH DE number 1445376
• New approximation algorithm for minimum Steiner tree problem
• A faster approximation algorithm for the Steiner problem in graphs
• Tighter Bounds for Graph Steiner Tree Approximation

Cited in

(2)

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

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

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