The Minimal Manhattan Network Problem in Three Dimensions

DOI10.1007/978-3-642-00202-1_32MaRDI QIDQ3605512zbMATH OpenOpenAlexFDO

Authors 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

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

Recommendations

• The transitive minimum Manhattan subnetwork problem in 3 dimensions
• The Minimum Manhattan Network Problem: A Fast Factor-3 Approximation
• The minimum Manhattan network problem: Approximations and exact solutions
• Algorithms and Computation
• Approximating a minimum Manhattan network
• A fixed-parameter algorithm for the minimum Manhattan network problem
• Exactly solvable and unsolvable shortest network problems in 3D-space

Cites work

• A Fast Algorithm for Constructing Sparse Euclidean Spanners
• A rounding algorithm for approximating minimum Manhattan networks
• Algorithms and Computation
• Approximating a minimum Manhattan network
• Fast Greedy Algorithms for Constructing Sparse Geometric Spanners
• scientific article; zbMATH DE number 1979512 (Why is no real title available?)
• Lower bounds for computing geometric spanners and approximate shortest paths
• NEW SPARSENESS RESULTS ON GRAPH SPANNERS
• On sparse spanners of weighted graphs
• The minimum Manhattan network problem: Approximations and exact solutions
• The transitive minimum Manhattan subnetwork problem in 3 dimensions

Cited in

(4)

• Approximating the generalized minimum Manhattan network problem
• Minimum Manhattan network is NP-complete
• The Minimum Manhattan Network Problem: A Fast Factor-3 Approximation
• The transitive minimum Manhattan subnetwork problem in 3 dimensions

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

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