Approximating a minimum Manhattan network

MaRDI QIDQ2748154zbMATH OpenFDO

Authors Joachim Gudmundsson, Giri Narasimhan, Christos Levcopoulos

Publication date 14 October 2001

Published in Nordic Journal of Computing (Search for Journal in Brave)

zbMATH Keywords

Manhattan network

Mathematics Subject Classification ID

Approximation algorithms (68W25) Deterministic network models in operations research (90B10)

Recommendations

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

Cited in

(25)

• Light orthogonal networks with constant geometric dilation
• Approximating the generalized minimum Manhattan network problem
• 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
• A rounding algorithm for approximating minimum Manhattan networks
• Approximation algorithms for network design problems
• A fixed-parameter algorithm for the minimum Manhattan network problem
• Greedy construction of 2-approximate minimum Manhattan networks
• Finding a manhattan path and related problems
• A Fast 2-Approximation Algorithm for the Minimum Manhattan Network Problem
• Greedy Construction of 2-Approximation Minimum Manhattan Network
• The Minimal Manhattan Network Problem in Three Dimensions
• An algorithm for the minimum variance point of a network
• scientific article; zbMATH DE number 1979512 (Why is no real title available?)
• MANHATTONIAN PROXIMITY IN A SIMPLE POLYGON
• Minimum Manhattan network is NP-complete
• The Minimum Manhattan Network Problem: A Fast Factor-3 Approximation
• Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
• Algorithms and Computation
• Dynamic programming approach to the generalized minimum Manhattan network problem
• Dynamic programming approach to the generalized minimum Manhattan network problem
• Linear-size planar Manhattan network for convex point sets
• On minimum generalized Manhattan connections
• A fast algorithm for connectivity graph approximation using modified Manhattan distance in dynamic networks
• The transitive minimum Manhattan subnetwork problem in 3 dimensions

This page was built for publication: Approximating a minimum Manhattan network

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