Bidirected minimum Manhattan network problem

DOI10.1002/NET.21719MaRDI QIDQ4565780zbMATHOpenAlexFDO

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

Publication date 13 June 2018

Published in Networks (Search for Journal in Brave)

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

zbMATH Keywords

distancesapproximation algorithmsnetwork designdirected networkManhattan networkrectilinear network

Mathematics Subject Classification ID

Deterministic network models in operations research (90B10)

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.

Recommendations

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

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)