engleski

Composite semirings and their applications dealing with path problems in graphs

Path problems in graphs can generally be formulated by using a suitable algebraic structure whose instances are called semirings. Each type of path problem requires a different instance of the structure. Solving a particular problem reduces to computing with matrices over the corresponding semiring. In this paper we propose a method for combining already known semirings into new ones. The obtained composite semirings can be applied to solve relatively complex path problems, involving explicit identification of optimal paths or multi-criteria optimization. We prove the correctness of our construction, and illustrate possible applications by examples.

graphs; path problems; algebraic approach; semirings; optimization

nije evidentirano