Skip to main content

Research Repository

Advanced Search

An exploration of graph algorithms and graph databases

Balaghan, Phininder

Authors

Phininder Balaghan



Contributors

Ken Hawick
Supervisor

Neil Andrew Gordon
Supervisor

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.

Citation

Balaghan, P. (2019). An exploration of graph algorithms and graph databases. (Thesis). University of Hull. Retrieved from https://hull-repository.worktribe.com/output/4221602

Thesis Type Thesis
Deposit Date May 28, 2019
Publicly Available Date Feb 23, 2023
Keywords Computer science
Public URL https://hull-repository.worktribe.com/output/4221602
Additional Information Department of Computer Science
Award Date May 1, 2019

Files

Thesis (2.7 Mb)
PDF

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




You might also like



Downloadable Citations