Nearly ETH-tight Algorithms for Planar Steiner Tree with Terminals on Few Faces

DOI10.1145/3371389zbMath1484.68166arXiv1811.06871OpenAlexW2963277542MaRDI QIDQ4987446

Erik Jan van Leeuwen, Sándor Kisfaludi-Bak, Jesper Nederlof

Publication date: 3 May 2021

Published in: ACM Transactions on Algorithms, Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1811.06871

zbMATH Keywords

planar graphslower boundSteiner treeparameterized algorithmsexact algorithmsexponential time hypothesis

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Nonnumerical algorithms (68W05) Graph theory (including graph drawing) in computer science (68R10)

Related Items (6)

Lower Bounds for Dominating Set in Ball Graphs and for Weighted Dominating Set in Unit-Ball Graphs ⋮ The homogeneous broadcast problem in narrow and wide strips. II: Lower bounds ⋮ Implications, conflicts, and reductions for Steiner trees ⋮ On Geometric Set Cover for Orthants ⋮ Implications, conflicts, and reductions for Steiner trees ⋮ A Framework for Exponential-Time-Hypothesis--Tight Algorithms and Lower Bounds in Geometric Intersection Graphs

This page was built for publication: Nearly ETH-tight Algorithms for Planar Steiner Tree with Terminals on Few Faces