Subclass of the Steiner problems on a plane with rectilinear metric

DOI10.1007/BF01078826MaRDI QIDQ4730786zbMATH OpenFDO

Authors V. A. Trubin

Publication date 1985

Published in Cybernetics (Search for Journal in Brave)

zbMATH Keywords

NP-completeSteiner tree problem

Mathematics Subject Classification ID

Trees (05C05) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20)

Recommendations

• The Steiner tree problem
• Improved Approximations for the Steiner Tree Problem
• Shortest trees and Steiner trees with rectilinear distances
• scientific article; zbMATH DE number 8006
• On exact solutions for the rectilinear Steiner tree problem. I: Theoretical results

Cites work

• scientific article; zbMATH DE number 3314878 (Why is no real title available?)
• The Rectilinear Steiner Tree Problem is $NP$-Complete

Cited in

(10)

• scientific article; zbMATH DE number 3984918 (Why is no real title available?)
• The Rectilinear Steiner Arborescence Problem Is NP-Complete
• On the Steiner property for planar minimizing clusters. The isotropic case
• The Steiner tree problem in orientation metrics
• The rectilinear class Steiner tree problem for intervals on two parallel lines
• Optimal competitiveness for the rectilinear Steiner arborescence problem
• A rounding algorithm for approximating minimum Manhattan networks
• The rectilinear Steiner arborescence problem
• On the solution of the generalized steiner problem by the subgradient method
• On the complexity of the Steiner problem

This page was built for publication: Subclass of the Steiner problems on a plane with rectilinear metric

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