2026-08-16T09:51:57Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:5931 2024-03-06T10:37:18Z ddc:004 open_access

Subexponential Algorithms for Rectilinear Steiner Tree and Arborescence Problems Fomin, Fedor Kolay, Sudeshna Lokshtanov, Daniel Panolan, Fahad Saurabh, Saket Rectilinear graphs Steiner arborescence parameterized algorithms A rectilinear Steiner tree for a set T of points in the plane is a tree which connects T using horizontal and vertical lines. In the Rectilinear Steiner Tree problem, input is a set T of n points in the Euclidean plane (R^2) and the goal is to find an rectilinear Steiner tree for T of smallest possible total length. A rectilinear Steiner arborecence for a set T of points and root r in T is a rectilinear Steiner tree S for T such that the path in S from r to any point t in T is a shortest path. In the Rectilinear Steiner Arborescense problem the input is a set T of n points in R^2, and a root r in T, the task is to find an rectilinear Steiner arborescence for T, rooted at r of smallest possible total length. In this paper, we give the first subexponential time algorithms for both problems. Our algorithms are deterministic and run in 2^{O(sqrt{n}log n)} time. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Fedor Fomin and Sudeshna Kolay and Daniel Lokshtanov and Fahad Panolan and Saket Saurabh 2016 Is Part Of LIPIcs, Volume 51, 32nd International Symposium on Computational Geometry (SoCG 2016) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SoCG.2016.39 urn:nbn:de:0030-drops-59310 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2016.39 eng https://creativecommons.org/licenses/by/3.0/legalcode