liu.seSearch for publications in DiVA
Change search
ReferencesLink to record
Permanent link

Direct link
On the Complexity of Finding Spanner Paths
Linköping University, Department of Computer and Information Science, Artificial Intelligence and Intergrated Computer systems. Linköping University, The Institute of Technology. ORCID iD: 0000-0002-2849-3316
2013 (English)In: Booklet of Abstracts, The European Workshop on Computational Geometry (EuroCG) / [ed] Sandor P. Fekete, 2013, 77-80Conference paper, Abstract (Refereed)
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.

Keyword [en]
Spanners, Euclidean Distance Approximation, Computational Geometry, Complexity Classification, Combinatorial Optimization
National Category
Computer Science
URN: urn:nbn:se:liu:diva-93332OAI: diva2:624158
The 29th European Workshop on Computational Geometry (EuroCG), March 17-20, Braunschweig, Germany
Available from2013-05-30 Created:2013-05-30 Last updated:2013-06-03Bibliographically approved

Open Access in DiVA

fulltext(290 kB)100 downloads
File information
File name FULLTEXT02.pdfFile size 290 kBChecksum SHA-512
Type fulltextMimetype application/pdf

Other links

Booklet of Abstracts

Search in DiVA

By author/editor
Nilsson, Mikael
By organisation
Artificial Intelligence and Intergrated Computer systemsThe Institute of Technology
Computer Science

Search outside of DiVA

GoogleGoogle Scholar
Total: 100 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Total: 69 hits
ReferencesLink to record
Permanent link

Direct link