Trustworthy Systems

Hopscotch—reaching the target hop by hop

Authors

Peter Hoefner and Annabelle McIver

NICTA

UNSW

Macquarie University

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.

BibTeX Entry

  @article{Hoefner_McIver_14,
    author           = {H\"ofner, Peter and McIver, Annabelle},
    doi              = {j.jlap.2014.02.009},
    journal          = {Journal of Logical and Algebraic Methods in Programming (JLAMP)},
    month            = apr,
    number           = {2},
    pages            = {212--224},
    paperurl         = {https://trustworthy.systems/publications/nicta_full_text/7524.pdf},
    publisher        = {Springer},
    series           = {Lecture Notes in Computer Science},
    title            = {Hopscotch---Reaching the Target Hop by Hop},
    volume           = {83},
    year             = {2014}
  }

Download