The transitive minimum Manhattan subnetwork problem in 3 dimensions

DOI10.1016/J.DAM.2009.06.025MaRDI QIDQ968145zbMATH OpenOpenAlexFDO

Authors 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

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

Recommendations

• Minimum Manhattan network is NP-complete
• Minimum Manhattan network is NP-complete
• The Minimal Manhattan Network Problem in Three Dimensions
• The minimum Manhattan network problem: Approximations and exact solutions

Cites work

• scientific article; zbMATH DE number 1979512 (Why is no real title available?)
• scientific article; zbMATH DE number 1445377 (Why is no real title available?)
• A rounding algorithm for approximating minimum Manhattan networks
• Algorithms and Computation
• Approximating a minimum Manhattan network
• Optimization, approximation, and complexity classes
• The Rectilinear Steiner Tree Problem is $NP$-Complete
• The minimum Manhattan network problem: Approximations and exact solutions

Cited in

(4)

• Minimum Manhattan network is NP-complete
• A connectivity graph generation approach for Manhattan path calculation in detailed facility layout
• Minimum Manhattan network is NP-complete
• The Minimal Manhattan Network Problem in Three Dimensions

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

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