Greedy Construction of 2-Approximation Minimum Manhattan Network

DOI10.1007/978-3-540-92182-0_4zbMATH Open1183.68744OpenAlexW1640191719MaRDI QIDQ3596702FDOQ3596702

Authors: Zeyu Guo, He Sun, Hong Zhu 

Publication date: 29 January 2009

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

Full work available at URL: https://doi.org/10.1007/978-3-540-92182-0_4

Recommendations

• Greedy construction of 2-approximate minimum Manhattan networks
• A Fast 2-Approximation Algorithm for the Minimum Manhattan Network Problem
• scientific article; zbMATH DE number 1979512
• The minimum Manhattan network problem: Approximations and exact solutions
• Approximating a minimum Manhattan network

zbMATH Keywords

approximation algorithmgreedy strategyMinimum Manhattan Network

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Approximation methods and heuristics in mathematical programming (90C59) Approximation algorithms (68W25)

Cited In (8)

• Minimum Manhattan network is NP-complete
• Greedy construction of 2-approximate minimum Manhattan networks
• Minimum Manhattan network problem in normed planes with polygonal balls: a factor 2.5 approximation algorithm
• The minimum Manhattan network problem: Approximations and exact solutions
• Dynamic programming approach to the generalized minimum Manhattan network problem
• Algorithms and Computation
• Approximating a minimum Manhattan network
• A Fast 2-Approximation Algorithm for the Minimum Manhattan Network Problem

This page was built for publication: Greedy Construction of 2-Approximation Minimum Manhattan Network

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