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

Direct link
On the Complexity of Finding Spanner Paths
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)98 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: 98 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: 67 hits
ReferencesLink to record
Permanent link

Direct link