onr:"swepub:oai:DiVA.org:liu-93332"
Search: onr:"swepub:oai:DiVA.org:liu-93332" > On the Complexity o...
- 1 of 1
- Previous record
- Next record
- To hitlist
On the Complexity of Finding Spanner Paths
-
- Nilsson, Mikael, 1977- (author)
- Linköpings universitet,Artificiell intelligens och integrerade datorsystem,Tekniska högskolan
- (creator_code:org_t)
- 2013
- 2013
- English.
- In: Booklet of Abstracts, The European Workshop on Computational Geometry (EuroCG). ; , s. 77-80
- Conference paper (peer-reviewed)
Abstract
Subject headings
Close
- 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.
Subject headings
- NATURVETENSKAP -- Data- och informationsvetenskap -- Datavetenskap (hsv//swe)
- NATURAL SCIENCES -- Computer and Information Sciences -- Computer Sciences (hsv//eng)
Keyword
- Spanners
- Euclidean Distance Approximation
- Computational Geometry
- Complexity Classification
- Combinatorial Optimization
Publication and Content Type
- ref (subject category)
- kon (subject category)
To the university's database
- 1 of 1
- Previous record
- Next record
- To hitlist
Find more in SwePub
- By the author/editor
- Nilsson, Mikael, ...
- About the subject
-
- NATURAL SCIENCES
- NATURAL SCIENCES
- and Computer and Inf ...
- and Computer Science ...
- Articles in the publication
- Booklet of Abstr ...
- By the university
- Linköping University
Search outside SwePub
- Extend your search to:
- Google Book Search
- Google Scholar
Kungliga biblioteket hanterar dina personuppgifter i enlighet med EU:s dataskyddsförordning (2018), GDPR. Läs mer om hur det funkar här.
Så här hanterar KB dina uppgifter vid användning av denna tjänst.
- Copyright © LIBRIS - National Library Systems
- LIBRIS.kb.se
