The Minimal Manhattan Network Problem in Three Dimensions

DOI10.1007/978-3-642-00202-1_32zbMath1211.68514OpenAlexW1550261019MaRDI QIDQ3605512

Xavier Muñoz, Sebastian Seibert, Walter Unger

Publication date: 24 February 2009

Published in: WALCOM: Algorithms and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-00202-1_32

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)

Related Items (3)

Approximating the generalized minimum Manhattan network problem ⋮ Approximating minimum Manhattan networks in higher dimensions ⋮ Minimum Manhattan network is NP-complete

Cites Work

• The transitive minimum Manhattan subnetwork problem in 3 dimensions
• On sparse spanners of weighted graphs
• The minimum Manhattan network problem: Approximations and exact solutions
• A rounding algorithm for approximating minimum Manhattan networks
• Fast Greedy Algorithms for Constructing Sparse Geometric Spanners
• A Fast Algorithm for Constructing Sparse Euclidean Spanners
• NEW SPARSENESS RESULTS ON GRAPH SPANNERS
• Algorithms and Computation
• Lower bounds for computing geometric spanners and approximate shortest paths
• Unnamed Item
• Unnamed Item

This page was built for publication: The Minimal Manhattan Network Problem in Three Dimensions