Hopscotch - reaching the target hop by hop

Peter Höfner*, Annabelle McIver

*Corresponding author for this work

Research output: Contribution to journalArticle

Abstract

Abstract Concrete and abstract relation algebras have widespread applications in computer science. One of the most famous is graph theory. Classical relations, however, only reason about connectivity, not about the length of a path between nodes. Generalisations of relation algebra, such as the min-plus algebra, use numbers allowing the treatment of weighted graphs. In this way one can for example determine the length of shortest paths (e.g. Dijkstra's algorithm). In this paper we treat matrices that carry even more information, such as the "next hop" on a path towards a destination. In this way we can use algebra not only for determining the length of paths, but also the concrete path. We show how paths can be reconstructed from these matrices, hop by hop. We further sketch an application for message passing in wireless networks.

Original languageEnglish
Article number397
Pages (from-to)212-224
Number of pages13
JournalJournal of Logical and Algebraic Methods in Programming
Volume83
Issue number2
DOIs
Publication statusPublished - 7 Aug 2014

Fingerprint Dive into the research topics of 'Hopscotch - reaching the target hop by hop'. Together they form a unique fingerprint.

  • Cite this