Bidirected minimum Manhattan network problem

DOI10.1002/NET.21719zbMATH Open1390.90098arXiv1107.1359OpenAlexW1671344423MaRDI QIDQ4565780FDOQ4565780

Victor Chepoi, Karim Nouioua, Yann Vaxès, Nicolas Catusse

Publication date: 13 June 2018

Published in: Networks (Search for Journal in Brave)

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.

Full work available at URL: https://arxiv.org/abs/1107.1359

Recommendations

• Algorithms and Computation
• A rounding algorithm for approximating minimum Manhattan networks
• scientific article; zbMATH DE number 1979512
• Approximating minimum Manhattan networks in higher dimensions
• Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques

zbMATH Keywords

distancesapproximation algorithmsnetwork designdirected networkManhattan networkrectilinear network

Mathematics Subject Classification ID

Deterministic network models in operations research (90B10)

This page was built for publication: Bidirected minimum Manhattan network problem

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