Rooted Graph Programs

Detlef Plump; Christopher  Bak

doi:10.14279/tuj.eceasst.54.780.778

Rooted Graph Programs

Detlef Plump, Christopher Bak

Computer Science

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Abstract

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.

Original language	English
Title of host publication	Proceedings 7th International Workshop on Graph Based Tools (GraBaTs 2012)
Editors	Christian Krause, Bernhard Westfechtel
Place of Publication	Berlin
Number of pages	12
DOIs	https://doi.org/10.14279/tuj.eceasst.54.780.778
Publication status	Published - 2012
Event	7th International Workshop on Graph Based Tools (GraBaTs 2012) - Bremen, Germany Duration: 24 Sept 2012 → …

Publication series

Name	Electronic Communications of the EASST
Publisher	Technische Universität Berlin
Volume	54

Workshop

Workshop	7th International Workshop on Graph Based Tools (GraBaTs 2012)
Country/Territory	Germany
City	Bremen
Period	24/09/12 → …

Keywords

Graph programs
rooted graphs
time complexity
constant-time graph matching
graph colouring

Access to Document

10.14279/tuj.eceasst.54.780.778Licence: Unspecified

BakPlump.GraBaTs.12Final published version, 199 KBLicence: CC BY

http://journal.ub.tu-berlin.de/eceasst/article/view/780Licence: Unspecified

Cite this

@inproceedings{ba7f8fd0549446b9a7f2cd1a3e86f292,

title = "Rooted Graph Programs",

abstract = "We present an approach for programming with graph transformation rulesin 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.",

keywords = "Graph programs, rooted graphs, time complexity, constant-time graph matching , graph colouring",

author = "Detlef Plump and Christopher Bak",

year = "2012",

doi = "10.14279/tuj.eceasst.54.780.778",

language = "English",

series = "Electronic Communications of the EASST",

publisher = "Technische Universit{\"a}t Berlin",

editor = "Christian Krause and Bernhard Westfechtel",

booktitle = "Proceedings 7th International Workshop on Graph Based Tools (GraBaTs 2012)",

note = "7th International Workshop on Graph Based Tools (GraBaTs 2012) ; Conference date: 24-09-2012",

}

TY - GEN

T1 - Rooted Graph Programs

AU - Plump, Detlef

AU - Bak, Christopher

PY - 2012

Y1 - 2012

N2 - We present an approach for programming with graph transformation rulesin 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.

AB - We present an approach for programming with graph transformation rulesin 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.

KW - Graph programs

KW - rooted graphs

KW - time complexity

KW - constant-time graph matching

KW - graph colouring

U2 - 10.14279/tuj.eceasst.54.780.778

DO - 10.14279/tuj.eceasst.54.780.778

M3 - Conference contribution

T3 - Electronic Communications of the EASST

BT - Proceedings 7th International Workshop on Graph Based Tools (GraBaTs 2012)

A2 - Krause, Christian

A2 - Westfechtel, Bernhard

CY - Berlin

T2 - 7th International Workshop on Graph Based Tools (GraBaTs 2012)

Y2 - 24 September 2012

ER -