Spelling suggestions: "subject:"euclidean asistance approximation"" "subject:"euclidean asistance eapproximation""
1 |
On the Complexity of Finding Spanner PathsNilsson, Mikael January 2013 (has links)
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.
|
Page generated in 0.1366 seconds