Nearly ETH-tight Algorithms for Planar Steiner Tree with Terminals on Few Faces
From MaRDI portal
Publication:4987446
DOI10.1145/3371389zbMath1484.68166arXiv1811.06871MaRDI QIDQ4987446
Erik Jan van Leeuwen, Jesper Nederlof, Sándor Kisfaludi-Bak
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
planar graphs; lower bound; Steiner tree; parameterized algorithms; exact algorithms; exponential time hypothesis
68W40: Analysis of algorithms
68W05: Nonnumerical algorithms
68R10: Graph theory (including graph drawing) in computer science