scientific article; zbMATH DE number 3985248

MaRDI QIDQ3749073zbMATH OpenFDO

Authors Luděk Kučera, Maurizio Talamo, Alberto Marchetti-Spaccamela, Marco Protasi

Publication date 1986

zbMATH Keywords

finding minimum Steiner treespolynomial algorithms

Mathematics Subject Classification ID

Trees (05C05) Random graphs (graph-theoretic aspects) (05C80) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• A faster approximation algorithm for the Steiner problem in graphs
• New approximation algorithm for minimum Steiner tree problem
• scientific article; zbMATH DE number 3918122
• On the value of a random minimum weight Steiner tree
• scientific article; zbMATH DE number 139910

Cited in

(7)

• Shortest paths in linear time on minor-closed graph classes, with an application to Steiner tree approximation
• Steiner's problem in graphs: Heuristic methods
• The competitiveness of randomized algorithms for on-line Steiner tree and on-line spanning tree problems
• Analysis of Steiner subtrees of random trees for traceroute algorithms
• Near optimal bounds for Steiner trees in the hypercube
• Shortest‐path metric approximation for random subgraphs
• A sharp threshold for minimum bounded-depth and bounded-diameter spanning trees and Steiner trees in random networks

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 Q3749073)