scientific article; zbMATH DE number 139919

zbMATH Open0768.68189MaRDI QIDQ4028261FDOQ4028261

Authors Bernard M. Waxman 

Publication date 28 March 1993

zbMATH Keywords

approximation algorithmsapproximation schemesSteiner tree problemworst-case performanceRayward-Smith's algorithm

Mathematics Subject Classification ID

Trees (05C05) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• scientific article; zbMATH DE number 1445376
• scientific article; zbMATH DE number 1305435
• A New Approximation Algorithm for the Steiner Tree Problem with Performance Ratio 5/3
• A faster approximation algorithm for the Steiner problem in graphs
• scientific article; zbMATH DE number 742979

Cited in

(5)

• Worst-case performance of Rayward-Smith's Steiner tree heuristic
• How Many Steiner Terminals Can You Connect in 20 Years?
• Strong Steiner tree approximations in practice
• Approximating Alternative Solutions
• Contraction-based Steiner tree approximations in practice

This page was built for publication:

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