On spanners of geometric graphs
Public Deposited- Resource Type
- Creator
- Abstract
Given a connected geometric graph G, we consider the problem of constructing a t-spanner of G having the minimum number of edges. We prove that for every t with 1 1+1/t) edges. This bound almost matches the known upper bound, which states that every connected weighted graph with n vertices contains a t-spanner with O(tn1+2/(t+1)) edges. We also prove that the problem of deciding whether a given geometric graph contains a t-spanner with at most K edges is NP-hard. Previously, this NP-hardness result was only known for non-geometric graphs.
- Language
- Publisher
- Identifier
- Citation
- Gudmundsson, J. (Joachim), & Smid, M. (2006). On spanners of geometric graphs. doi:10.1007/11785293_36
- Date Created
- 2006-01-01
Relations
- In Collection:
Items
Thumbnail | Title | Date Uploaded | Visibility | Actions |
---|---|---|---|---|
|
densespanner.pdf | 2022-08-26 | Public | Download |