Bidirected minimum Manhattan network problem | Zendy

Catusse Nicolas | Zendy; Chepoi Victor | Zendy; Nouioua Karim | Zendy; Vaxès Yann | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

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

This content is not available in your region!

Continue researching here.

Having issues? You can contact us here

Accelerating Research