The transitive minimum Manhattan subnetwork problem in 3 dimensions

DOI10.1016/j.dam.2009.06.025zbMath1226.05098OpenAlexW2044395823MaRDI QIDQ968145

Birgit Engels

Publication date: 5 May 2010

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2009.06.025

zbMATH Keywords

grid graphManhattan network1-spanner3 dimensions

Mathematics Subject Classification ID

Network design and communication in computer systems (68M10) Planar graphs; geometric and topological aspects of graph theory (05C10)

Related Items (2)

A connectivity graph generation approach for Manhattan path calculation in detailed facility layout ⋮ The Minimal Manhattan Network Problem in Three Dimensions

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Optimization, approximation, and complexity classes
• The minimum Manhattan network problem: Approximations and exact solutions
• A rounding algorithm for approximating minimum Manhattan networks
• The Rectilinear Steiner Tree Problem is $NP$-Complete
• Algorithms and Computation

This page was built for publication: The transitive minimum Manhattan subnetwork problem in 3 dimensions