Naslov
Some results dealing with the algebraic approach to 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 8th International Symposium on Operational Research in Slovenia (SOR '05) / Zadnik Stirn, Lidija ; Drobne, Samo - Ljubljana : Slovensko društvo informatika, 2005, 13-22

Skup
8th International Symposium on Operational Research in Slovenia (SOR '05)

Mjesto i datum
Nova Gorica, Slovenija, 28.09.2005. - 30.09.2005

Vrsta sudjelovanja
Predavanje

Vrsta recenzije
Međunarodna recenzija

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

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 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.

Izvorni jezik
Engleski

Znanstvena područja
Matematika, Računarstvo

POVEZANOST RADA