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 language | English (US) |
|---|---|
| Pages (from-to) | 413-423 |
| Number of pages | 11 |
| Journal | Networks |
| Volume | 15 |
| Issue number | 4 |
| DOIs | |
| State | Published - 1985 |
| Externally published | Yes |
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
- APA
- Author
- BIBTEX
- Harvard
- Standard
- RIS
- Vancouver