Back to search

University of York

Speeding up Graph Programs

Abstract

dc:description.abstract

This thesis presents an improvement in rule-based graph programming which enables the design of graph programs that achieve the time complexity of imperative linear-time algorithms. Achieving such complexity in conventional languages using graph transformation rules is challenging due to the high cost of graph matching. Previous work demonstrated that with rooted rules, certain algorithms can be executed in linear time using the graph programming language GP 2. However, for non-destructive algorithms that preserve the structure of input graphs, achieving linear runtime required input graphs to be both connected and of bounded node degree. In this thesis, we overcome these limitations by enhancing the graph data structure generated by the GP 2 compiler and exploiting this new structure within the programs. We present four case studies: a program that checks graph’s connectedness, a program that two-colours a graph, a cycle detection program, and a program that computes the shortest weighted distances from a single source to all other nodes in a weighted graph. The first three programs run in linear time on both connected and disconnected input graphs with arbitrary node degrees. The fourth program achieves a time complexity comparable to that of conventional implementations in imperative programming languages. For each program, we provide a formal analysis of its correctness and complexity, supplemented by empirical benchmarking.

Degree

thesis:*
Name dc:type.qualificationname
M.Sc by research
Level dc:type.qualificationlevel
masters
Grantor dc:publisher.institution
University of York
Year dc:date.issued
2025

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Ismaili Alaoui, Ziad
Advisor dc:contributor.advisor
  • Plump, Detlef

Rights

Language dc:language.dcterms_iso639_2
eng

Chain of custody

source
Harvested from
White Rose University Consortium
Base URL
etheses.whiterose.ac.uk/cgi/oai2
Last updated
2026-11-18
Source record
OAI-PMH GetRecord
related terms
citation

Ismaili Alaoui, Ziad. Speeding up Graph Programs. masters thesis, University of York, 2025.