Subexponential Algorithms for Rectilinear Steiner Tree and Arborescence Problems

Fomin, Fedor V. and Lokshtanov, Daniel and Kolay, Sudeshna and Panolan, Fahad and Saurabh, Saket (2020) Subexponential Algorithms for Rectilinear Steiner Tree and Arborescence Problems. ACM Transactions on Algorithms, 16 (2). pp. 1-37. ISSN 1549-6325

Text
ACM_Transactions_on_Algorithms.pdf - Published Version
Available under License Creative Commons Attribution.
Download (870kB)

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={z1,z2,…, zn} of n points in the Euclidean plane (R2), 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 R2, 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 2O(√ nlog n) time.

[error in script]

IITH Creators:

IITH Creators	ORCiD
Panolan, Fahad	https://orcid/org/0000-0001-6213-8687

Item Type:

Article

Additional Information:

A preliminary version of this article appeared in the proceedings of SoCG 2016. This project received funding from the European Research Council (ERC) under the Euro- pean Union’s Horizon 2020 research and innovation programme (grant agreement no. 819416) and from the Norwegian Research Council via grant MULTIVAL. S. Saurabh was supported by Swarnajayanti Fellowship grant DST/SJF/MSA-01/2017-18. Authors’ addresses: F. V. Fomin, Department of Informatics, University of Bergen, PB 7803, Bergen, 5020, Norway; email: fedor.fomin@uib.no; D. Lokshtanov, University of California Santa Barbara, Santa Barbara, CA; email: daniello@ucsb.edu; S. Kolay, Department of Computer Science and Engineering, Indian Institute of Technology Kharagpur, Kharagpur, 721302, India; email: sudeshna.kolay@gmail.com; F. Panolan, Department of Computer Science and Engineering, Indian Institute of Technology Hyderabad, Kandi, Sangareddy, 502285, India; email: fahad@iith.ac.in; S. Saurabh, Institute of Mathematical Sciences, Homi Bhabha National Institute, Theoretical Computer Science Department, IRL 2000 ReLaX, Chennai, 600113, India, and Department of Informatics, University of Bergen, PB 7803, Bergen, 5020, Norway; email: saket@imsc.res.in. Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from permissions@acm.org. © 2020 Association for Computing Machinery. 1549-6325/2020/03-ART21 $15.00 https://doi.org/10.1145/3381420

Uncontrolled Keywords:

rectilinear Steiner arborescence; Rectilinear Steiner tree; subexponential exact algorithm; treewidth algorithm

Subjects:

Computer science
Computer science > Algorithm Analysis

Divisions:

Department of Computer Science & Engineering

Depositing User:

. LibTrainee 2021

Date Deposited:

23 Nov 2022 12:15

Last Modified:

23 Nov 2022 12:15