1 Search Results for "Campbell, Graham"

Linear-Time Graph Algorithms in GP 2

Authors: Graham Campbell, Brian Courtehoute, and Detlef Plump

Published in: LIPIcs, Volume 139, 8th Conference on Algebra and Coalgebra in Computer Science (CALCO 2019)

GP 2 is an experimental programming language based on graph transformation rules which aims to facilitate program analysis and verification. However, implementing graph algorithms efficiently in a rule-based language is challenging because graph pattern matching is expensive. GP 2 mitigates this problem by providing rooted rules which, under mild conditions, can be matched in constant time. In this paper, we present linear-time GP 2 programs for three problems: tree recognition, binary directed acyclic graph (DAG) recognition, and topological sorting. In each case, we show the correctness of the program, prove its linear time complexity, and also give empirical evidence for the linear run time. For DAG recognition and topological sorting, the linear behaviour is achieved by implementing depth-first search strategies based on an encoding of stacks in graphs.

Cite as

Graham Campbell, Brian Courtehoute, and Detlef Plump. Linear-Time Graph Algorithms in GP 2. In 8th Conference on Algebra and Coalgebra in Computer Science (CALCO 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 139, pp. 16:1-16:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

  author =	{Campbell, Graham and Courtehoute, Brian and Plump, Detlef},
  title =	{{Linear-Time Graph Algorithms in GP 2}},
  booktitle =	{8th Conference on Algebra and Coalgebra in Computer Science (CALCO 2019)},
  pages =	{16:1--16:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-120-7},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{139},
  editor =	{Roggenbach, Markus and Sokolova, Ana},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CALCO.2019.16},
  URN =		{urn:nbn:de:0030-drops-114440},
  doi =		{10.4230/LIPIcs.CALCO.2019.16},
  annote =	{Keywords: Graph transformation, rooted graph programs, GP 2, linear-time algorithms, depth-first search, topological sorting}
  • Refine by Author
  • 1 Campbell, Graham
  • 1 Courtehoute, Brian
  • 1 Plump, Detlef

  • Refine by Classification
  • 1 Theory of computation → Design and analysis of algorithms

  • Refine by Keyword
  • 1 GP 2
  • 1 Graph transformation
  • 1 depth-first search
  • 1 linear-time algorithms
  • 1 rooted graph programs
  • Show More...

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2019

Questions / Remarks / Feedback

Feedback for Dagstuhl Publishing

Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail