Browsing by Author "Schnizler, Michael"

Filter results by typing the first few letters
Now showing 1 - 1 of 1
  • Thumbnail Image
    ItemOpen Access
    The Generalized Minimum Manhattan Network Problem
    (2015) Schnizler, Michael
    In this thesis we consider the Generalized Minimum Manhattan Network Problem: given a set containing n pairs of points in R2 or Rd, the goal is to find a rectilinear network of minimal length which contains a path of minimal length (a so-called Manhattan path) between the two points of each pair. We restrict our search to a discrete subspace and show that under specific conditions an optimal solution can be found in polynomial time using a dynamic program. The conditions concern the intersection graph of the bounding boxes of the pairs. Its maximum degree as well as the treewidth must be bounded by two constants which are independent of n. Finally, we present a simple greedy algorithm for practical purposes.