The transitive minimum Manhattan subnetwork problem in 3 dimensions

DOI10.1016/J.DAM.2009.06.025zbMATH Open1226.05098OpenAlexW2044395823MaRDI QIDQ968145FDOQ968145

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)

Cites Work

• Optimization, approximation, and complexity classes
• The Rectilinear Steiner Tree Problem is $NP$-Complete
• The minimum Manhattan network problem: Approximations and exact solutions
• A rounding algorithm for approximating minimum Manhattan networks
• Approximating a minimum Manhattan network
• Title not available (Why is that?)
• Algorithms and Computation
• Title not available (Why is that?)

Cited In (2)

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

   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 👍 👎
• Approximating minimum Manhattan networks in higher 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)