A comparison of search times oncompressed and uncompressedgraphs

Abstract: 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.