Return to search

On the Complexity of Finding Spanner Paths

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.

Identiferoai:union.ndltd.org:UPSALLA1/oai:DiVA.org:liu-93332
Date January 2013
CreatorsNilsson, Mikael
PublisherLinköpings universitet, Artificiell intelligens och integrerad datorsystem, Linköpings universitet, Tekniska högskolan
Source SetsDiVA Archive at Upsalla University
LanguageEnglish
Detected LanguageEnglish
TypeConference paper, info:eu-repo/semantics/conferenceObject, text
Formatapplication/pdf
Rightsinfo:eu-repo/semantics/openAccess
RelationBooklet of Abstracts, The European Workshop on Computational Geometry (EuroCG), p. 77-80

Page generated in 0.0018 seconds