Linear-Time Graph Programs for Unbounded-Degree Graphs

Achieving the complexity of graph algorithms in conventional languages with programs based on graph transformation rules is challenging because of the cost of graph matching. Previous work demonstrated that with so-called rooted rules, certain algorithms can be executed in linear time using the graph programming language GP 2. However, for non-destructive algorithms which retain the structure of input graphs, achieving a linear runtime required that input graphs have a bounded node degree. In this paper, we show how to overcome this restriction by enhancing the graph data structure generated by the GP 2 compiler and exploiting the new structure in programs. As a case study, we present a 2-colouring program that runs in linear time on connected input graphs with arbitrary node degrees. We prove the linear time complexity and also provide empirical evidence in the form of timings for various classes of input graphs.