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)
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.
Spanners, Euclidean Distance Approximation, Computational Geometry, Complexity Classification, Combinatorial Optimization
National CategoryComputer Science
IdentifiersURN: urn:nbn:se:liu:diva-93332OAI: oai:DiVA.org:liu-93332DiVA: diva2:624158
The 29th European Workshop on Computational Geometry (EuroCG), March 17-20, Braunschweig, Germany