Skip to main navigation Skip to search Skip to main content

Probabilistic partitioning algorithms for the rectilinear steiner problem

Research output: Contribution to journal › Article › peer-review

Abstract

Based on the probabilistic approach introduced by Karp [14], we present two partitioning algorithms for the approximate solution of large instances of the rectilinear Steiner problem in the plane. The algorithms subdivide a set of given points into small groups, construct a minimum rectilinear Steiner tree for each small group, and then patch the subtrees together to form a near‐optimum rectilinear Steiner tree for the given points. Suppose there are n given points, uniformly distributed over the unit square [0,1] × [0,1] and spanned by a minimum rectilinear Steiner tree To. Then for any given integer t > 0, the first algorithm runs in O(f(t)n + n log n) time and produces a rectilinear Steiner tree T1 such that \documentclass{article}\pagestyle{empty}\begin{document}$ \left({|T_1 |/|T_0 |} \right) \le 1 + O\left({\sqrt {1/t}} \right) $\end{document} with probability approaching 1 as n → ∞, while the second algorithm has an expected running time of O(g(t)n) and it also produces a rectilinear Steiner tree T2 such that \documentclass{article}\pagestyle{empty}\begin{document}$ \left({|T_2 |/|T_0 |} \right) \le 1 + O\left({\sqrt {1/t}} \right) $\end{document} with probability approaching 1 as n → ∞.

Original languageEnglish (US)
Pages (from-to)413-423
Number of pages11
JournalNetworks
Volume15
Issue number4
DOIs
StatePublished - 1985
Externally publishedYes

ASJC Scopus subject areas

  • Information Systems
  • Computer Networks and Communications

Fingerprint

Dive into the research topics of 'Probabilistic partitioning algorithms for the rectilinear steiner problem'. Together they form a unique fingerprint.

Cite this