TY - GEN

T1 - Dynamic programming approach to the generalized minimum manhattan network problem

AU - Masumura, Yuya

AU - Oki, Taihei

AU - Yamaguchi, Yutaro

N1 - Publisher Copyright:
© Springer Nature Switzerland AG 2020.

PY - 2020

Y1 - 2020

N2 - We study the generalized minimum Manhattan network (GMMN) problem: given a set $$P$$ of pairs of points in the Euclidean plane $$\mathbb R^2$$, we are required to find a minimum-length geometric network which consists of axis-aligned segments and contains a shortest path in the $$L:1$$ metric (a so-called Manhattan path) for each pair in $$P$$. This problem commonly generalizes several NP-hard network design problems that admit constant-factor approximation algorithms, such as the rectilinear Steiner arborescence (RSA) problem, and it is open whether so does the GMMN problem. As a bottom-up exploration, Schnizler (2015) focused on the intersection graphs of the rectangles defined by the pairs in $$P$$, and gave a polynomial-time dynamic programming algorithm for the GMMN problem whose input is restricted so that both the treewidth and the maximum degree of its intersection graph are bounded by constants. In this paper, as the first attempt to remove the degree bound, we provide a polynomial-time algorithm for the star case, and extend it to the general tree case based on an improved dynamic programming approach.

AB - We study the generalized minimum Manhattan network (GMMN) problem: given a set $$P$$ of pairs of points in the Euclidean plane $$\mathbb R^2$$, we are required to find a minimum-length geometric network which consists of axis-aligned segments and contains a shortest path in the $$L:1$$ metric (a so-called Manhattan path) for each pair in $$P$$. This problem commonly generalizes several NP-hard network design problems that admit constant-factor approximation algorithms, such as the rectilinear Steiner arborescence (RSA) problem, and it is open whether so does the GMMN problem. As a bottom-up exploration, Schnizler (2015) focused on the intersection graphs of the rectangles defined by the pairs in $$P$$, and gave a polynomial-time dynamic programming algorithm for the GMMN problem whose input is restricted so that both the treewidth and the maximum degree of its intersection graph are bounded by constants. In this paper, as the first attempt to remove the degree bound, we provide a polynomial-time algorithm for the star case, and extend it to the general tree case based on an improved dynamic programming approach.

UR - http://www.scopus.com/inward/record.url?scp=85089233169&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85089233169&partnerID=8YFLogxK

U2 - 10.1007/978-3-030-53262-8_20

DO - 10.1007/978-3-030-53262-8_20

M3 - Conference contribution

AN - SCOPUS:85089233169

SN - 9783030532611

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 237

EP - 248

BT - Combinatorial Optimization - 6th International Symposium, ISCO 2020, Revised Selected Papers

A2 - Baïou, Mourad

A2 - Gendron, Bernard

A2 - Günlük, Oktay

A2 - Mahjoub, A. Ridha

PB - Springer

T2 - 6th International Symposium on Combinatorial Optimization, ISCO 2020

Y2 - 4 May 2020 through 6 May 2020

ER -