engleski

Some results dealing with the algebraic approach to 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 two recent results dealing with the algebraic approach to path problems based on semirings. The first part of the paper introduces a method for combining already known semirings into new ones. The obtained composite semirings correspond to relatively complex path problems involving explicit identification of optimal paths or multi-criteria optimization. The second part of the paper describes a distributed algorithm for solving path problems, which has been implemented on a network of computers. Thanks to its specification in terms of an arbitrary semiring, the algorithm can be applied to different types of simple or complex path problems.

directed graphs; path problems; algebraic approach; semirings; optimization; distributed algorithms

nije evidentirano