The Minimum Manhattan Network Problem: A Fast Factor-3 Approximation

DOI10.1007/11589440_2MaRDI QIDQ5449750zbMATH OpenOpenAlexFDO

Authors Marc Benkert, Alexander Wolff, Florian Widmann

Publication date 18 March 2008

Published in Discrete and Computational Geometry (Search for Journal in Brave)

Full work available at URL https://publikationen.bibliothek.kit.edu/1000003164

Mathematics Subject Classification ID

Computational aspects related to convexity (52B55) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Approximation algorithms (68W25)

Recommendations

• The minimum Manhattan network problem: Approximations and exact solutions
• A Fast 2-Approximation Algorithm for the Minimum Manhattan Network Problem
• Algorithms and Computation
• The Minimal Manhattan Network Problem in Three Dimensions
• Approximating the generalized minimum Manhattan network problem
• Approximating the generalized minimum Manhattan network problem
• Approximating a minimum Manhattan network
• A fixed-parameter algorithm for the minimum Manhattan network problem
• scientific article; zbMATH DE number 1979512
• Minimum Manhattan network problem in normed planes with polygonal balls: a factor 2.5 approximation algorithm

Cited in

(6)

• The minimum Manhattan network problem: Approximations and exact solutions
• A rounding algorithm for approximating minimum Manhattan networks
• Geometric Spanner of Objects under L 1 Distance
• A Fast 2-Approximation Algorithm for the Minimum Manhattan Network Problem
• The Minimal Manhattan Network Problem in Three Dimensions
• Minimum Manhattan network is NP-complete

This page was built for publication: The Minimum Manhattan Network Problem: A Fast Factor-3 Approximation

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