Subclass of the Steiner problems on a plane with rectilinear metric

DOI10.1007/BF01078826zbMATH Open0681.68075MaRDI QIDQ4730786FDOQ4730786

V. A. Trubin

Publication date: 1985

Published in: Cybernetics (Search for Journal in Brave)

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

zbMATH Keywords

NP-completeSteiner tree problem

Mathematics Subject Classification ID

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

Cites Work

• The Rectilinear Steiner Tree Problem is $NP$-Complete
• Title not available (Why is that?)

Cited In (11)

• The Steiner tree problem in orientation metrics
• Optimal Competitiveness for the Rectilinear Steiner Arborescence Problem
• On the Steiner property for planar minimizing clusters. The isotropic case
• The rectilinear class Steiner tree problem for intervals on two parallel lines
• On the complexity of the Steiner problem
• On the solution of the generalized steiner problem by the subgradient method
• Flip distance between triangulations of a simple polygon is NP-complete
• A rounding algorithm for approximating minimum Manhattan networks
• The Rectilinear Steiner Arborescence Problem Is NP-Complete
• The rectilinear Steiner arborescence problem
• Title not available (Why is that?)

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)