Skip to Main content Skip to Navigation
Journal articles

Bidirected minimum Manhattan network problem

Nicolas Catusse 1 Victor Chepoi 2 Karim Nouioua 2 Yann Vaxès 2
1 G-SCOP_ROSP [2016-2019] - Recherche Opérationnelle pour les Systèmes de Production [2016-2019]
G-SCOP [2016-2019] - Laboratoire des sciences pour la conception, l'optimisation et la production [2016-2019]
2 ACRO - Algorithmique, Combinatoire et Recherche Opérationnelle
LIS - Laboratoire d'Informatique et Systèmes
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.
Complete list of metadatas

Cited literature [20 references]  Display  Hide  Download

https://hal.archives-ouvertes.fr/hal-02268714
Contributor : Victor Chepoi <>
Submitted on : Wednesday, May 20, 2020 - 12:38:25 PM
Last modification on : Wednesday, August 5, 2020 - 3:00:53 AM

File

1107.1359.pdf
Files produced by the author(s)

Identifiers

Citation

Nicolas Catusse, Victor Chepoi, Karim Nouioua, Yann Vaxès. Bidirected minimum Manhattan network problem. Networks, Wiley, 2017, 69 (2), pp.167-178. ⟨10.1002/net.21719⟩. ⟨hal-02268714⟩

Share

Metrics

Record views

233

Files downloads

103