Abstract
In the Steiner point removal (SPR) problem, we are given a (weighted) graph G and a subset T of its vertices called terminals, and the goal is to compute a (weighted) graph H on T that is a minor of G, such that the distance between every pair of terminals is preserved to within some small multiplicative factor, that is called the stretch of H. It has been shown that on general graphs we can achieve stretch O(log |T|) [Filtser, 2018]. On the other hand, the best-known stretch lower bound is 8 [Chan-Xia-Konjevod-Richa, 2006], which holds even for trees. In this work, we show an improved lower bound of (Equation presented).
| Original language | English (US) |
|---|---|
| Pages | 694-698 |
| Number of pages | 5 |
| DOIs | |
| State | Published - 2024 |
| Externally published | Yes |
| Event | 35th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2024 - Alexandria, United States Duration: Jan 7 2024 → Jan 10 2024 |
Conference
| Conference | 35th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2024 |
|---|---|
| Country/Territory | United States |
| City | Alexandria |
| Period | 1/7/24 → 1/10/24 |
Bibliographical note
Publisher Copyright:Copyright © 2024 This paper is available under the CC-BY 4.0 license.
Fingerprint
Dive into the research topics of 'An (Equation presented) Lower Bound for Steiner Point Removal'. Together they form a unique fingerprint.Cite this
- APA
- Standard
- Harvard
- Vancouver
- Author
- BIBTEX
- RIS