LiU Electronic Press
Download:
File size:
2125 kb
Format:
application/pdf
Author:
Nilsson, Mikael (Institutionen för datavetenskap, Naturvetenskapliga fakulteten, Lunds universitet)
Title:
Spanneröar och spannervägar
Publication type:
Student thesis
Language:
Swedish
Level:
Independent thesis Advanced level (degree of Master (One Year)), 20 credits / 30 HE credits
Undergraduate subject:
Computer science (20-credit final thesis, D level)
Pages:
126
Year of publ.:
2009
URI:
urn:nbn:se:liu:diva-93331
Permanent link:
http://urn.kb.se/resolve?urn=urn:nbn:se:liu:diva-93331
ISRN:
-
Subject category:
Natural Sciences
Computer Science
Keywords(en) :
t-path, Spanner path, graph, spanner, NP-complete, complexity reduction, algorithm, heuristics, finite calculus.
Abstract(en) :

In this Master Thesis the possibility to efficiently divide a graph into spanner islands is examined. Spanner islands are islands of the graph that fulfill the spanner condition, that the distance between two nodes via the edges in the graph cannot be too far, regulated by the stretch constant, compared to the Euclidian distance between them. In the resulting division the least number of nodes connecting to other islands is sought-after. Different heuristics are evaluated with the conclusion that for dense graphs a heuristic using MAX-FLOW to divide problematic nodes gives the best result whereas for sparse graphs a heuristic using the single-link clustering method performs best. The problem of finding a spanner path, a path fulfilling the spanner condition, between two nodes is also investigated. The problem is proven to be NP-complete for a graph of size n if the spanner constant is greater than n^(1+1/k)*k^0.5 for some integer k. An algorithm with complexity O(2^(0.822n)) is given. A special type of graph where all the nodes are located on integer locations along the real line is investigated. An algorithm to solve this problem is presented with a complexity of O(2^((c*log n)^2))), where c is a constant depending only on the spanner constant. For instance, the complexity O(2^((5.32*log n)^2))) can be reached for stretch 1.5.

Abstract(sv) :

I det här magisterarbetet undersöks om det är möjligt att på ett effektivt sätt dela upp en graf i spanneröar, dvs. öar som uppfyller spanneregenskapen som består i att avståndet mellan två noder via grafens bågar inte får vara för stort i förhållande till det euklidiska avståndet mellan noderna. Att hitta en uppdelning som skapar så få kontaktpunkter mellan öarna som möjligt eftersöks. Ett antal heuristiker testas och utvärderas med resultatet att en heuristik som använder sig av MAX-FLOW för att dela upp noder som bryter mot spannervillkoret presterar bäst för täta grafer medan en heuristik av typ single-link clustering presterar bäst för glesa grafer. I arbetet visas att problemet att finna en spannerväg, en väg där noderna som passeras uppfyller spannervillkoret, mellan två noder i en graf av storlek n är NP-komplett om spannerkonstanten är större än n^(1+1/k)*k^0.5 för något heltal k. En algoritm för att hitta spannervägar med komplexiteten O(2^(0.822n)) presenteras. Ett specialproblem där grafen ligger längs tallinjen och bara har noder på heltalspunkter studeras slutligen och här konstrueras en algoritm med komplexiteten O(2^((c*log n)^2))) där c är en konstant som beror på spannerkonstanten. Till exempel nås O(2^((5.32*log n)^2))) för stretch 1.5.

Presentation:
2009-10-28, 10:00 (Swedish)
Supervisor:
Levcopoulos, Christos (Lunds Universitet)
Examiner:
Lingas, Andrzej (Lunds Universitet)
Available from:
2013-05-30
Created:
2013-05-30
Last updated:
2013-05-30
Statistics:
18 hits
FILE INFORMATION
File size:
2125 kb
Mimetype:
application/pdf
Type:
fulltext
Statistics:
44 hits