@inproceedings{8615038937bb4c1abfca277076c79cec,

title = "Towards Graph Programs for Graph Algorithms",

abstract = "Graph programs as introduced by Habel and Plump [8] provide a simple yet computationally complete language for computing functions and relations on graphs. We extend this language such that numerical computations on labels can be conveniently expressed. Rather than resorting to some kind of attributed graph transformation, we introduce conditional rule schemata which are instantiated to (conditional) double-pushout rules over ordinary graphs. A guiding principle in our language extension is syntactic and semantic simplicity. As a case study for the use of extended graph programs, we present and analyse two versions of Dijkstra's shortest path algorithm. The first program consists of just three rule schemata and is easily proved to be correct but can be exponential in the number of rule applications. The second program is a refinement of the first which is essentially deterministic and uses at most a quadratic number of rule applications.",

keywords = "TRANSFORMATION",

author = "Detlef Plump and Sandra Steinert",

year = "2004",

doi = "10.1007/978-3-540-30203-2_11",

language = "English",

isbn = "3-540-23207-9",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "128--143",

editor = "H Ehrig and G Engels and F ParisiPresicce and G Rozenberg",

booktitle = "Proceedings 2nd International Conference on Graph Transformation (ICGT 2004)",

address = "Germany",

note = "2nd International Conference on Graph Transformations ; Conference date: 28-09-2004 Through 02-10-2004",

}