LiU Electronic Press
Download:
File size:
290 kb
Format:
application/pdf
Author:
Nilsson, Mikael (Linköping University, Department of Computer and Information Science, Artificial Intelligence and Intergrated Computer systems) (Linköping University, The Institute of Technology)
Title:
On the Complexity of Finding Spanner Paths
Department:
Linköping University, Department of Computer and Information Science, Artificial Intelligence and Intergrated Computer systems
Linköping University, The Institute of Technology
Publication type:
Conference paper, Abstract (Refereed)
Language:
English
In:
Booklet of Abstracts, The European Workshop on Computational Geometry (EuroCG)
Editor:
Sandor P. Fekete
Conference:
The 29th European Workshop on Computational Geometry (EuroCG), March 17-20, Braunschweig, Germany
Pages:
77-80
Year of publ.:
2013
URI:
urn:nbn:se:liu:diva-93332
Permanent link:
http://urn.kb.se/resolve?urn=urn:nbn:se:liu:diva-93332
Subject category:
Computer Science
Keywords(en) :
Spanners, Euclidean Distance Approximation, Computational Geometry, Complexity Classification, Combinatorial Optimization
Abstract(en) :

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.

Available from:
2013-05-30
Created:
2013-05-30
Last updated:
2013-06-03
Statistics:
64 hits
FILE INFORMATION
File size:
290 kb
Mimetype:
application/pdf
Type:
fulltext
Statistics:
71 hits
Version:
Publisherʼs version