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

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • oxford
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
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-80 p.Conference paper, Oral presentation with published 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.

Place, publisher, year, edition, pages
2013. 77-80 p.
Keyword [en]
Spanners, Euclidean Distance Approximation, Computational Geometry, Complexity Classification, Combinatorial Optimization
National Category
Computer Science
Identifiers
URN: urn:nbn:se:liu:diva-93332OAI: oai:DiVA.org:liu-93332DiVA: diva2:624158
Conference
The 29th European Workshop on Computational Geometry (EuroCG), March 17-20, Braunschweig, Germany
Available from: 2013-05-30 Created: 2013-05-30 Last updated: 2013-06-03Bibliographically approved

Open Access in DiVA

On the Complexity of Finding Spanner Paths(290 kB)170 downloads
File information
File name FULLTEXT02.pdfFile size 290 kBChecksum SHA-512
2f548f9e8557201806c5b737dc688870acaa4b24ee09eff2d37bfd6b8a137c07784e522273af82bfd5246e0597cbb29f494758c7fb1c28fabc4e9a7935f3d941
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: 170 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: 203 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • oxford
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf