Subexponential Algorithms for Rectilinear Steiner Tree and Arborescence Problems

Abstract

A rectilinear Steiner tree for a set K of points in the plane is a tree that connects k using horizontal and vertical lines. In the Rectilinear Steiner Tree problem, the input is a set K={z₁,z₂,…, z_n} of n points in the Euclidean plane (R²), and the goal is to find a rectilinear Steiner tree for k of smallest possible total length. A rectilinear Steiner arborescence for a set k of points and a root r ∈ K is a rectilinear Steiner tree T for K such that the path in T from r to any point z ∈ K is a shortest path. In the Rectilinear Steiner Arborescence problem, the input is a set K of n points in R², and a root r ∈ K, and the task is to find a rectilinear Steiner arborescence for K, rooted at r of smallest possible total length. In this article, we design deterministic algorithms for these problems that run in 2^O(√nlogn) time.