Document Open Access Logo

Subexponential Algorithms for Rectilinear Steiner Tree and Arborescence Problems

Authors Fedor Fomin, Sudeshna Kolay, Daniel Lokshtanov, Fahad Panolan, Saket Saurabh

PDF
Thumbnail PDF

File

LIPIcs.SoCG.2016.39.pdf
  • Filesize: 0.53 MB
  • 15 pages

Document Identifiers

Author Details

Fedor Fomin
Sudeshna Kolay
Daniel Lokshtanov
Fahad Panolan
Saket Saurabh

Cite AsGet BibTex

Fedor Fomin, Sudeshna Kolay, Daniel Lokshtanov, Fahad Panolan, and Saket Saurabh. Subexponential Algorithms for Rectilinear Steiner Tree and Arborescence Problems. In 32nd International Symposium on Computational Geometry (SoCG 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 51, pp. 39:1-39:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
https://doi.org/10.4230/LIPIcs.SoCG.2016.39

Abstract

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.
Keywords
  • Rectilinear graphs
  • Steiner arborescence
  • parameterized algorithms

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Andreas Björklund, Thore Husfeldt, Petteri Kaski, and Mikko Koivisto. Fourier meets Möbius: fast subset convolution. In Proceedings of the 39th Annual ACM Symposium on Theory of Computing (STOC), pages 67-74, New York, 2007. ACM. Google Scholar
  2. Marcus Brazil and Martin Zachariasen. Optimal Interconnection Trees in the Plane: Theory, Algorithms and Applications. Springer, 2015. Google Scholar
  3. Marek Cygan, Fedor V. Fomin, Łukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michał Pilipczuk, and Saket Saurabh. Parameterized Algorithms. Springer-Verlag, Berlin, 2015. Google Scholar
  4. Linda L. Deneen, Gary M. Shute, and Clark D. Thomborson. A probably fast, provably optimal algorithm for rectilinear Steiner trees. Random Structures Algorithms, 5(4):535-557, 1994. Google Scholar
  5. Stuart E. Dreyfus and Robert A. Wagner. The Steiner problem in graphs. Networks, 1(3):195-207, 1971. URL: http://dx.doi.org/10.1002/net.3230010302.
  6. Bernhard Fuchs, Walter Kern, Daniel Mölle, Stefan Richter, Peter Rossmanith, and Xinhui Wang. Dynamic programming for minimum Steiner trees. Theory of Computing Systems, 41(3):493-500, 2007. URL: http://dx.doi.org/10.1007/s00224-007-1324-4.
  7. Joseph L. Ganley. Computing optimal rectilinear Steiner trees: a survey and experimental evaluation. Discrete Appl. Math., 90(1-3):161-171, 1999. Google Scholar
  8. Joseph L. Ganley and James P. Cohoon. Improved computation of optimal rectilinear Steiner minimal trees. Internat. J. Comput. Geom. Appl., 7(5):457-472, 1997. URL: http://dx.doi.org/10.1142/S0218195997000272.
  9. M. R. Garey and D. S. Johnson. The rectilinear Steiner tree problem is NP-complete. SIAM J. Appl. Math., 32(4):826-834, 1977. Google Scholar
  10. Qian-Ping Gu and Hisao Tamaki. Improved bounds on the planar branchwidth with respect to the largest grid minor size. Algorithmica, 64(3):416-453, 2012. URL: http://dx.doi.org/10.1007/s00453-012-9627-5.
  11. M. Hanan. On Steiner’s problem with rectilinear distance. SIAM J. Appl. Math., 14:255-265, 1966. Google Scholar
  12. Frank K Hwang. On Steiner minimal trees with rectilinear distance. SIAM J. Appl. Math., 30(1):104-114, 1976. Google Scholar
  13. Frank K. Hwang, Dana S. Richards, and Pawel Winter. The Steiner tree problem, volume 53 of Annals of Discrete Mathematics. North-Holland Publishing Co., Amsterdam, 1992. Google Scholar
  14. Philip N. Klein and Dániel Marx. A subexponential parameterized algorithm for Subset TSP on planar graphs. In Proceedings of the 25th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1812-1830. SIAM, 2014. Google Scholar
  15. L. Nastansky, S. M. Selkow, and N. F. Stewart. Cost-minimal trees in directed acyclic graphs. Z. Operations Res. Ser. A-B, 18:A59-A67, 1974. Google Scholar
  16. Jesper Nederlof. Fast polynomial-space algorithms using inclusion-exclusion. Algorithmica, 65(4):868-884, 2013. URL: http://dx.doi.org/10.1007/s00453-012-9630-x.
  17. Marcin Pilipczuk, Michał Pilipczuk, Piotr Sankowski, and Erik Jan van Leeuwen. Subexponential-time parameterized algorithm for Steiner tree on planar graphs. In Proc. of the 30th International Symp. on Theoretical Aspects of Computer Science (STACS), volume 20 of Leibniz International Proceedings in Informatics (LIPIcs), pages 353-364. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2013. Google Scholar
  18. Marcin Pilipczuk, Michal Pilipczuk, Piotr Sankowski, and Erik Jan van Leeuwen. Network sparsification for Steiner problems on planar and bounded-genus graphs. In Proc. 55th Annual Symp. on Foundations of Computer Science (FOCS), pages 276-285. IEEE, 2014. Google Scholar
  19. Hans Jürgen Prömel and Angelika Steger. The Steiner Tree Problem. Advanced Lectures in Mathematics. Friedr. Vieweg &Sohn, Braunschweig, 2002. Google Scholar
  20. Weiping Shi and Chen Su. The Rectilinear Steiner Arborescence Problem Is NP-Complete. SIAM J. Comput., 35(3):729-740, 2005. URL: http://dx.doi.org/10.1137/S0097539704371353.
  21. Clark D Thomborson, Linda L Deneen, and Gary M Shute. Computing a rectilinear steiner minimal tree in n^O (√n) time. In Parallel Algorithms and Architectures, pages 176-183. Springer, 1987. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact