Bidirected minimum Manhattan network problem
Preprint
Abstract
In the bidirected minimum Manhattan network problem, given a set T of n terminals in the plane, we need to construct a network N(T) of minimum total length with the property that the edges of N(T) are axis-parallel and oriented in a such a way that every ordered pair of terminals is connected in N(T) by a directed Manhattan path. In this paper, we present a polynomial factor 2 approximation algorithm for the bidirected minimum Manhattan network problem.Keywords
All Related Versions
This publication has 8 references indexed in Scilit:
- Minimum Manhattan Network Problem in Normed Planes with Polygonal Balls: A Factor 2.5 Approximation AlgorithmAlgorithmica, 2011
- Roundtrip spanners and roundtrip routing in directed graphsACM Transactions on Algorithms, 2008
- The minimum Manhattan network problem: Approximations and exact solutionsComputational Geometry, 2005
- A Rounding Algorithm for Approximating Minimum Manhattan NetworksLecture Notes in Computer Science, 2005
- Picking Alignments from (Steiner) TreesJournal of Computational Biology, 2003
- On network characterization of and optimal broadcasting in the Manhattan Street Network2002
- Optimal communication algorithms for manhattan street networksDiscrete Applied Mathematics, 1998
- Routing in the Manhattan Street NetworkIEEE Transactions on Communications, 1987