engleski

A catalogue of useful composite semirings for solving path problems in graphs

A wide variety of path problems in graphs can generally be formulated and solved by algebraic means. For this purpose, an abstract algebraic structure is introduced whose instances are called semirings. Each particular type of path problem is characterized by a different instance of the structure. This paper presents an extensive list of composite semirings, which are obtained by combining simpler semirings known from literature. The paper demonstrates how the listed composite semirings can be applied to solve relatively complex path problems involving explicit identification of optimal paths and/or multi-criteria optimization. The text can be considered as an appendix to a previous paper where composite semirings had been introduced for the first time.

directed graphs; path problems; algebraic approach; semirings; composite semirings; identification of optimal paths; multi-criteria optimization

nije evidentirano