Subclass of the Steiner problems on a plane with rectilinear metric

DOI10.1007/BF01078826zbMath0681.68075MaRDI QIDQ4730786

V. A. Trubin

Publication date: 1985

Published in: Cybernetics (Search for Journal in Brave)

zbMATH Keywords

Steiner tree problemNP-complete

Mathematics Subject Classification ID

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

Related Items

Optimal Competitiveness for the Rectilinear Steiner Arborescence Problem ⋮ The Steiner tree problem in orientation metrics ⋮ Flip distance between triangulations of a simple polygon is NP-complete ⋮ The rectilinear Steiner arborescence problem ⋮ A rounding algorithm for approximating minimum Manhattan networks

Cites Work

• The Rectilinear Steiner Tree Problem is $NP$-Complete
• Unnamed Item