Semirings and their application to path computation in graphs - 01/30/2009

Niloofar Fazlollahi

In this talk I will first introduce abstract algebraic structures called semirings which are introduced to symbolize and generalize optimization problems in fields like graph theory ordiscrete event dynamic systems. I will further describe the contents of a relevant paper on generic shortest-distance algorithms which uses semiring structures. I present their algorithm and their analysis results. Then, I will suggest how through use of specific semirings (and/or) some modifications to their algorithm we can achieve various guaranteed path optimizations as desired. Time allowing, I may explain the problem of k-shortest distance as stated in the paper and their generic solution. The mentioned paper title is: "Semiring frameworks and algorithms for shortest-distance problems"