|title:||Rooted Graph Programs|
|company:||University of York|
|keywords:||Graph Programming, Algorithmic Complexity|
|type:||DESC Research Internship|
The graph programming language GP  allows to solve graph problems at a high level of abstraction, based on nondeterministic applications of graph transformation rules. The nondeterminism, however, makes graph matching a costly operation which may cause poor execution times for graph programs.
To make graph programs fast, the PhD thesis , the paper  and the monograph  propose a technique which removes much of the nondeterminism in graph matching: viz. to contol the matching process by a unique root node in each rule and in the host graph. This allows constant-time graph matching on graphs of bounded node degree. The purpose of this project is to carry out a case study which tries out this technique on some selected graph algorithms. The running time of the resulting programs shall be determined theoretically - assuming a suitable implementation of GP - and compared practically with that of conventional GP programs using the current GP implementation .
- D. Plump: The Graph Programming Language GP. In Proc. Algebraic Informatics (CAI 2009), volume 5725 of Lecture Notes in Computer Science, pages 99-122. © Springer-Verlag, 2009
- M. Dodds: Graph Transformation and Pointer Structures. PhD thesis, The University of York, 2008.
- M. Dodds and D. Plump: Graph Transformation in Constant Time. Proc. International Conference on Graph Transformation (ICGT 2006), Lecture Notes in Computer Science 4178, pages 367-382. © Springer-Verlag, 2006