An improved algorithm for the minimum Manhattan network problem

DOI10.1007/3-540-36136-7_31MaRDI QIDQ4427856zbMATH OpenFDO

Authors Ryo Kato, Keiko Imai, T. Asano

Publication date 14 September 2003

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL http://link.springer.de/link/service/series/0558/bibs/2518/25180344.htm

Mathematics Subject Classification ID

Approximation algorithms (68W25) Deterministic network models in operations research (90B10) Combinatorial optimization (90C27) Approximation methods and heuristics in mathematical programming (90C59)

Recommendations

• A Fast 2-Approximation Algorithm for the Minimum Manhattan Network Problem
• Approximating a minimum Manhattan network
• Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
• Greedy construction of 2-approximate minimum Manhattan networks

Cited in

(19)

• A shortest-path algorithm for Manhattan graphs
• 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
• Approximating a minimum Manhattan network
• A fixed-parameter algorithm for the minimum Manhattan network problem
• Greedy construction of 2-approximate minimum Manhattan networks
• 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
• Bidirected minimum Manhattan network problem
• 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
• The transitive minimum Manhattan subnetwork problem in 3 dimensions

This page was built for publication: An improved algorithm for the minimum Manhattan network problem

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