Rooted Graph Programs


  • Detlef Plump Department of Computer Science The University of York
  • Christopher Bak Department of Computer Science The University of York



We present an approach for programming with graph transformation rules in which programs can be as efficient as programs in imperative languages. The basic idea is to equip rules and host graphs with distinguished nodes, so-called roots, and to match roots in rules with roots in host graphs. This enables graph transformation rules to be matched in constant time, provided that host graphs have a bounded node degree (which in practice is often the case). Hence, for example, programs with a linear bound on the number of rule applications run in truly linear time. We demonstrate the feasibility of this approach with a case study in graph colouring.




How to Cite

D. Plump and C. Bak, “Rooted Graph Programs”, eceasst, vol. 54, Nov. 2012.