Advanced

Spanneröar och spannervägar

Nilsson, Mikael LU (2009) DAT299 20092
Computer Science
Abstract
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... (More)
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. (Less)
Abstract (Swedish)
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... (More)
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. (Less)
Please use this url to cite or link to this publication:
author
Nilsson, Mikael LU
supervisor
organization
course
DAT299 20092
year
type
H1 - Master's Degree (One Year)
subject
keywords
Spanner path, t-path, graph, spanner, NP-complete, reduction, algorithm, heuristics, finite calculus.
report number
LU-DV-EX:2009-135
ISSN
1651-6389
language
Swedish
id
1785932
date added to LUP
2011-02-11 10:02:57
date last changed
2011-02-11 10:02:57
@misc{1785932,
  abstract     = {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.},
  author       = {Nilsson, Mikael},
  issn         = {1651-6389},
  keyword      = {Spanner path,t-path,graph,spanner,NP-complete,reduction,algorithm,heuristics,finite calculus.},
  language     = {swe},
  note         = {Student Paper},
  title        = {Spanneröar och spannervägar},
  year         = {2009},
}