Naslov
Solving path problems on a network of computers

Autori
Manger, Robert

Izvornik
Informatica: an international journal of computing and informatics (0350-5596) 26 (2002), 1; 91-100

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

Ključne riječi
graph theory; path problems; distributed algorithms; network computing; parallel virtual machine (PVM); experiments

Sažetak
Path problems are a family of optimization and enumeration problems, which reduce to generation or comparison of paths in graphs. Some examples are: checking the existence of a path between two given nodes, finding the shortest or the most reliable path, finding the path of maximum capacity, listing all paths, etc. In this paper we propose a distributed algorithm for solving path problems in directed graphs. The algorithm can easily be implemented on a network of computers. In the paper we also prove the correctness of the proposed algorithm. Next, we describe an actual network implementation based on the PVM package. Finally, we list some experimental results illustrating the performance of the implemented algorithm.

Izvorni jezik
Engleski

Znanstvena područja
Matematika, Računarstvo

POVEZANOST RADA