An exploration of graph algorithms and graph databases

Balaghan, Phininder

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. An exploration of graph algorithms and graph databases. (Thesis). University of Hull. 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