Naslov
Composite semirings and their applications dealing with path problems in graphs

Autori
Manger, Robert

Izvornik
Grazer mathematische Berichte (1016-7692) -348 (2005), 348; 31-40

Vrsta, podvrsta i kategorija rada
Radovi u časopisima, članak, znanstveni

Ključne riječi
graphs; path problems; algebraic approach; semirings; optimization

Sažetak
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.

Izvorni jezik
Engleski

Znanstvena područja
Matematika, Računarstvo

POVEZANOST RADA