New Results on Fault Tolerant Geometric Spanners

T. Lukovszki, in: Proceedings of the 6th Workshop on Algorithms an Data Structures (WADS’99), LNCS, 1999, pp. 193–204.

Download
No fulltext has been uploaded.
Conference Paper | Published | English
Author
Abstract
We investigate the problem of constructing spanners for a given set of points that are tolerant for edge/vertex faults. Let S be a set of $n$ points in the d-dimensional space and let k be an integer number. A k-edge/vertex fault tolerant spanner for S has the property that after the deletion of k arbitrary edges/vertices each pair of points in the remaining graph is still connected by a short path.<br><br>Recently it was shown that for each set S of n points there exists a k-edge/vertex fault tolerant spanner with O(k^2 n) edges which can be constructed in O(n log n + k^2 n) time. Furthermore, it was shown that for each set S of n points there exists a k-edge/vertex fault tolerant spanner whose degree is bouned by O(c^k+1) for some constant c.<br><br>Our first contribution is a construction of a k-vertex fault tolerant spanner with O(kn) edges which is a tight bound. The computation takes O(n log^d-1 n + k n log log n) time. Then we show that the same k-vertex fault tolerant spanner is also k-edge fault tolerant. Thereafter, we construct a k-vertex fault tolerant spanner with O(k^2 n) edges whose degree is bounded by O(k^2). Finally, we give a more natural but stronger definition of k-edge fault tolerance which not necessarily can be satisfied if one allows only simple edges between the points of S. We investigate the question whether Steiner points help. We answer this question affirmatively and prove Theta(kn) bounds on the number of Steiner points and on the number of edges in such spanners.
Publishing Year
Proceedings Title
Proceedings of the 6th Workshop on Algorithms an Data Structures (WADS'99), LNCS
Page
193-204
ISSN
LibreCat-ID

Cite this

Lukovszki T. New Results on Fault Tolerant Geometric Spanners. In: Proceedings of the 6th Workshop on Algorithms an Data Structures (WADS’99), LNCS. ; 1999:193-204. doi:10.1007/3-540-48447-7_20
Lukovszki, T. (1999). New Results on Fault Tolerant Geometric Spanners. In Proceedings of the 6th Workshop on Algorithms an Data Structures (WADS’99), LNCS (pp. 193–204). https://doi.org/10.1007/3-540-48447-7_20
@inproceedings{Lukovszki_1999, title={New Results on Fault Tolerant Geometric Spanners}, DOI={10.1007/3-540-48447-7_20}, booktitle={Proceedings of the 6th Workshop on Algorithms an Data Structures (WADS’99), LNCS}, author={Lukovszki, Tamás}, year={1999}, pages={193–204} }
Lukovszki, Tamás. “New Results on Fault Tolerant Geometric Spanners.” In Proceedings of the 6th Workshop on Algorithms an Data Structures (WADS’99), LNCS, 193–204, 1999. https://doi.org/10.1007/3-540-48447-7_20.
T. Lukovszki, “New Results on Fault Tolerant Geometric Spanners,” in Proceedings of the 6th Workshop on Algorithms an Data Structures (WADS’99), LNCS, 1999, pp. 193–204.
Lukovszki, Tamás. “New Results on Fault Tolerant Geometric Spanners.” Proceedings of the 6th Workshop on Algorithms an Data Structures (WADS’99), LNCS, 1999, pp. 193–204, doi:10.1007/3-540-48447-7_20.

Export

Marked Publications

Open Data LibreCat

Search this title in

Google Scholar
ISBN Search