Greedy construction of 2-approximate minimum Manhattan networks

DOI10.1142/S0218195911003688zbMATH Open1231.05242OpenAlexW1996406174MaRDI QIDQ3089095FDOQ3089095

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

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

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)

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
• Title not available (Why is that?)
• 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)