Premium
Bidirected minimum Manhattan network problem
Author(s) -
Catusse Nicolas,
Chepoi Victor,
Nouioua Karim,
Vaxès Yann
Publication year - 2017
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.21719
Subject(s) - combinatorics , mathematics , path (computing) , set (abstract data type) , plane (geometry) , discrete mathematics , computer science , computer network , geometry , programming language
In the bidirected minimum Manhattan network problem , given a set T of n terminals in the plane, no two terminals on the same horizontal or vertical line, we need to construct a network N ( T ) of minimum total length with the property that the edges of N ( T ) belong to the axis‐parallel grid defined by T and are oriented in a such a way that every ordered pair of terminals is connected in N ( T ) by a directed Manhattan path. In this article, we present a polynomial factor 2‐approximation algorithm for the bidirected minimum Manhattan network problem. © 2016 Wiley Periodicals, Inc. NETWORKS, Vol. 69(2), 167–178 2017