Greedy Construction of 2-Approximation Minimum Manhattan Network

DOI10.1007/978-3-540-92182-0_4MaRDI QIDQ3596702zbMATH OpenOpenAlexFDO

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

zbMATH Keywords

approximation algorithmgreedy strategyMinimum Manhattan Network

Mathematics Subject Classification ID

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

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

Cited in

(8)

• 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
• Approximating a minimum Manhattan network
• Greedy construction of 2-approximate minimum Manhattan networks
• A Fast 2-Approximation Algorithm for the Minimum Manhattan Network Problem
• Minimum Manhattan network is NP-complete
• Algorithms and Computation
• Dynamic programming approach to the generalized 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)