Greedy construction of 2-approximate minimum Manhattan networks

DOI10.1142/S0218195911003688MaRDI QIDQ3089095zbMATH OpenOpenAlexFDO

Authors Zeyu Guo, He Sun, Hong Zhu

Publication date 23 August 2011

Published in International Journal of Computational Geometry & Applications (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1142/s0218195911003688

zbMATH Keywords

approximation algorithmsgreedy strategyminimum manhattan networks

Mathematics Subject Classification ID

Linear programming (90C05) Dynamic programming (90C39) Small world graphs, complex networks (graph-theoretic aspects) (05C82) Approximation algorithms (68W25)

Recommendations

• Greedy Construction of 2-Approximation Minimum Manhattan Network
• A Fast 2-Approximation Algorithm for the Minimum Manhattan Network Problem
• scientific article; zbMATH DE number 1979512
• Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
• Approximating a minimum Manhattan network

Cites work

• Finding efficient solutions for rectilinear distance location problems efficiently
• The minimum Manhattan network problem: Approximations and exact solutions

Cited in

(9)

• Linear-size planar Manhattan network for convex point sets
• The two‐median problem on Manhattan meshes
• scientific article; zbMATH DE number 1979512 (Why is no real title available?)
• Approximating the generalized minimum Manhattan network problem
• A shortest-path algorithm for Manhattan graphs
• A rounding algorithm for approximating minimum Manhattan networks
• Approximating a minimum Manhattan network
• A Fast 2-Approximation Algorithm for the Minimum Manhattan Network Problem
• Greedy Construction of 2-Approximation Minimum Manhattan Network

This page was built for publication: Greedy construction of 2-approximate minimum Manhattan networks

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