Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
A comparison of search times oncompressed and uncompressedgraphs
KTH, School of Computer Science and Communication (CSC).
KTH, School of Computer Science and Communication (CSC).
2015 (English)Independent thesis Basic level (degree of Bachelor), 10 credits / 15 HE creditsStudent thesis
Abstract [en]

This report researches whether it is possible to speed up search algorithmson general graphs by means of graph compression. To determineif this is possible the compression methods RPGraph, LZGraph, DSMand k2-tree were used in combination with the breadth rst search anddepth rst search algorithms. The search algorithms were run on graphsof dierent sizes, both in compressed and uncompressed form, and therun times were compared. The results showed that compression adds toomuch overhead in neighbour list retrieval times to be able to reduce searchtimes when both the uncompressed and compressed graphs can be heldin main memory.

Place, publisher, year, edition, pages
2015.
National Category
Computer Science
Identifiers
URN: urn:nbn:se:kth:diva-166454OAI: oai:DiVA.org:kth-166454DiVA: diva2:811126
Supervisors
Examiners
Available from: 2015-05-12 Created: 2015-05-11 Last updated: 2017-02-28Bibliographically approved

Open Access in DiVA

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

By organisation
School of Computer Science and Communication (CSC)
Computer Science

Search outside of DiVA

GoogleGoogle Scholar
Total: 87 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

urn-nbn

Altmetric score

urn-nbn
Total: 1086 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf