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

Autori
Manger, Robert

Vrsta, podvrsta i kategorija rada
Radovi u zbornicima skupova, cjeloviti rad (in extenso), znanstveni

Izvornik
Proceedings of the 11-th International Conference on Operational Research (KOI 2006 - Pula, Croatia, September 27-29, 2006) / Boljunčić, Valter ; Neralić, Luka ; Šorić, Kristina - Zagreb : Hrvatsko društvo za operacijska istraživanja (CRORS), 2008, 13-23

Skup
11-th International Conference on Operational Research (KOI 2006)

Mjesto i datum
Pula, Hrvatska, 27.07.2006. - 29.07.2006

Vrsta sudjelovanja
Predavanje

Vrsta recenzije
Međunarodna recenzija

Ključne riječi
directed graphs; path problems; algebraic approach; semirings; composite semirings; identification of optimal paths; multi-criteria optimization

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

Izvorni jezik
Engleski

Znanstvena područja
Matematika, Računarstvo

POVEZANOST RADA