Dynamic programming approach to the generalized minimum manhattan network problem

Yuya Masumura, Taihei Oki, Yutaro Yamaguchi

Research output: Chapter in Book/Report/Conference proceedingConference contribution

2 Citations (Scopus)


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.

Original languageEnglish
Title of host publicationCombinatorial Optimization - 6th International Symposium, ISCO 2020, Revised Selected Papers
EditorsMourad Baïou, Bernard Gendron, Oktay Günlük, A. Ridha Mahjoub
Number of pages12
ISBN (Print)9783030532611
Publication statusPublished - 2020
Event6th International Symposium on Combinatorial Optimization, ISCO 2020 - Montreal, Canada
Duration: May 4 2020May 6 2020

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume12176 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Conference6th International Symposium on Combinatorial Optimization, ISCO 2020

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • General Computer Science


Dive into the research topics of 'Dynamic programming approach to the generalized minimum manhattan network problem'. Together they form a unique fingerprint.

Cite this