  Implementing graph algorithms efficiently in a rule-based language is
challenging because graph pattern matching is expensive. In this paper, we
present a number of linear-time implementations of graph algorithms in GP 2, an
experimental programming language based on graph transformation rules which
aims to facilitate program analysis and verification. We focus on two classes
of rule-based graph programs: graph reduction programs which check some graph
property, and programs using a depth-first search to test some property or
perform an operation such as producing a 2-colouring or a topological sorting.
Programs of the first type run in linear time without any constraints on input
graphs while programs of the second type require input graphs of bounded degree
to run in linear time. Essential for achieving the linear time complexity are
so-called rooted rules in GP 2, which, in many situations, can be matched in
constant time. For each of our programs, we prove both correctness and
complexity, and also give empirical evidence for their run time.
