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

Direct link
Spanneröar och spannervägar
2009 (Swedish)Independent thesis Advanced level (degree of Master (One Year)), 20 credits / 30 HE creditsStudent thesis
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.

Place, publisher, year, pages
2009. , 126 p.
Keyword [en]
t-path, Spanner path, graph, spanner, NP-complete, complexity reduction, algorithm, heuristics, finite calculus.
National Category
Natural Sciences Computer Science
URN: urn:nbn:se:liu:diva-93331ISRN: -OAI: diva2:624155
Subject / course
Computer science (20-credit final thesis, D level)
2009-10-28, 10:00 (Swedish)
Available from2013-05-30 Created:2013-05-30 Last updated:2013-05-30Bibliographically approved

Open Access in DiVA

fulltext(2125 kB)49 downloads
File information
File name FULLTEXT01.pdfFile size 2125 kBChecksum SHA-512
Type fulltextMimetype application/pdf

Search in DiVA

By author/editor
Nilsson, Mikael
Natural SciencesComputer Science

Search outside of DiVA

GoogleGoogle Scholar
Total: 49 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: 22 hits
ReferencesLink to record
Permanent link

Direct link