The algebraic path problem is a generalization of the shortest path problem in graphs. Various
instances of this abstract problem have appeared in the literature and similar solutions have
been independently discovered and rediscovered. The repeated appearance of a problem is
evidence of its relevance. This book aims to help current and future researchers add this
powerful tool to their arsenal so that they can easily identify and use it in their own work.
Path problems in networks can be conceptually divided into two parts: A distillation of the
extensive theory behind the algebraic path problem and an exposition of a broad range of
applications. First of all the shortest path problem is presented so as to fix terminology and
concepts: existence and uniqueness of solutions robustness to parameter changes and
centralized and distributed computation algorithms. Then these concepts are generalized to the
algebraic context of semirings. Methods for creating new semirings useful for modeling new
problems are provided. A large part of the book is then devoted to numerous applications of
the algebraic path problem ranging from mobile network routing to BGP routing to social
networks. These applications show what kind of problems can be modeled as algebraic path
problems they also serve as examples on how to go about modeling new problems.This monograph
will be useful to network researchers engineers and graduate students. It can be used either
as an introduction to the topic or as a quick reference to the theoretical facts algorithms
and application examples. The theoretical background assumed for the reader is that of a
graduate or advanced undergraduate student in computer science or engineering. Some familiarity
with algebra and algorithms is helpful but not necessary. Algebra in particular is used as a
convenient and concise language to describe problems that are essentially combinatorial.Table
of Contents: Classical Shortest Path The Algebraic Path Problem Properties and Computation
of Solutions Applications Related Areas List of Semirings and Applications
