We study the complexity of finding so called spanner paths between arbitrary nodes in Euclidean graphs. We study both general Euclidean graphs and a special type of graphs called Integer Graphs. The problem is proven NP-complete for general Euclidean graphs with non-constant stretches (e.g. (2n)^(3/2) where n denotes the number of nodes in the graph). An algorithm solving the problem in O(2^(0.822n)) is presented. Integer graphs are simpler and for these special cases a better algorithm is presented. By using a partial order of so called Images the algorithm solves the spanner path problem using O(2^(c(\log n)^2)) time, where c is a constant depending only on the stretch.
| Identifer | oai:union.ndltd.org:UPSALLA1/oai:DiVA.org:liu-93332 |
| Date | January 2013 |
| Creators | Nilsson, Mikael |
| Publisher | Linköpings universitet, Artificiell intelligens och integrerad datorsystem, Linköpings universitet, Tekniska högskolan |
| Source Sets | DiVA Archive at Upsalla University |
| Language | English |
| Detected Language | English |
| Type | Conference paper, info:eu-repo/semantics/conferenceObject, text |
| Format | application/pdf |
| Rights | info:eu-repo/semantics/openAccess |
| Relation | Booklet of Abstracts, The European Workshop on Computational Geometry (EuroCG), p. 77-80 |
Page generated in 0.0023 seconds