Affordable Access

Publisher Website

Hopscotch—reaching the target hop by hop

Authors
Journal
The Journal of Logic and Algebraic Programming
1567-8326
Publisher
Elsevier
Volume
83
Issue
2
Identifiers
DOI: 10.1016/j.jlap.2014.02.009
Keywords
  • Routing
  • Semiring
  • Kleene Algebra
  • Path
Disciplines
  • Computer Science
  • Mathematics

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.

There are no comments yet on this publication. Be the first to share your thoughts.

Statistics

Seen <100 times
0 Comments

More articles like this

Hopscotch

Feb 17, 2010

Hopscotch

Jan 26, 2010

Hopscotch

Jan 11, 2010

Hopscotch

Jan 26, 2010
More articles like this..