...researching fundamentals of networking and communications


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"

r1 - 2009-01-30 - 20:09:30 - WeiyaoXiao

Laboratory of Networking and Information Systems
Photonics Building, Room 413
8 St Mary's Street,
Boston MA 02215

Initial web site created by Sachin Agarwal (ska@alum.bu.edu), Modified by Weiyao Xiao (weiyao@alum.bu.edu), Moved to TWiki backend by Ari Trachtenberg (trachten@bu.edu). Managed by Jiaxi Jin (jin@bu.edu).
Syndicate this site RSSATOM