scientific article; zbMATH DE number 426374

MaRDI QIDQ3137223zbMATH OpenFDO

Authors Alex Zelikovsky

Publication date 1 November 1993

zbMATH Keywords

networks with rectilinear distanceNP-completeshortest spanning treeSteiner problem

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

• An 11/6-approximation algorithm for the network Steiner problem
• scientific article; zbMATH DE number 1305435
• scientific article; zbMATH DE number 125502
• scientific article; zbMATH DE number 4049088
• An approximation algorithm for the Steiner connectivity problem
• A faster approximation algorithm for the Steiner problem in graphs
• A faster approximation algorithm for the Steiner problem in graphs
• scientific article; zbMATH DE number 895361
• scientific article; zbMATH DE number 1834686
• A note on A faster approximation algorithm for the Steiner problem in graphs

Cited in

(8)

• Rectilinear Steiner tree heuristics and minimum spanning tree algorithms using geographic nearest neighbors
• Fixed-parameter algorithms for rectilinear Steiner tree and rectilinear traveling salesman problem in the plane
• A practical algorithm for the minimum rectilinear Steiner tree
• On approximations for constructing 1-line minimum rectilinear Steiner trees in the Euclidean plane \(\mathbb{R}^2\)
• Probabilistic partitioning algorithms for the rectilinear steiner problem
• scientific article; zbMATH DE number 125502 (Why is no real title available?)
• scientific article; zbMATH DE number 1161391 (Why is no real title available?)
• Shortest trees and Steiner trees with rectilinear distances

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