An exploration of graph algorithms and graph databases

Balaghan, Phininder

Computer science
May 2019

Thesis or dissertation


Rights
© 2019 Phininder Balaghan. All rights reserved. No part of this publication may be reproduced without the written permission of the copyright holder.
Abstract

With data becoming larger in quantity, the need for complex, efficient algorithms to solve computationally complex problems has become greater. In this thesis we evaluate a selection of graph algorithms; we provide a novel algorithm for solving and approximating the Longest Simple Cycle problem, as well as providing novel implementations of other graph algorithms in graph database systems.

The first area of exploration is finding the Longest Simple Cycle in a graph problem. We propose two methods of finding the longest simple cycle. The first method is an exact approach based on a flow-based Integer Linear Program. The second is a multi-start local search heuristic which uses a simple depth-first search as a basis for a cycle, and improves this with four perturbation operators.

Secondly, we focus on implementing the Minimum Dominating Set problem into graph database systems. An unoptimised greedy heuristic solution to the Minimum Dominating Set problem is implemented into a client-server system using a declarative query language, an embedded database system using an imperative query language and a high level language as a direct comparison. The performance of the graph back-end on the database systems is evaluated. The language expressiveness of the query languages is also explored. We identify limitations of the query methods of the database system, and propose a function that increases the functionality of the queries.

Publisher
Department of Computer Science
Supervisor
Hawick, Ken; Gordon, Neil Andrew
Qualification level
Doctoral
Qualification name
PhD
Language
English
Extent
2 MB
Identifier
hull:17300
QR Code