Algorithms for some graph problems on a distributed computational model |
| |
| Affiliation: | 1. Department of Aquatic Ecology, Netherlands Institute of Ecology (NIOO-KNAW), Droevendaalsesteeg 10, 6708 PB Wageningen, Netherlands;2. Department of Earth Sciences, Faculty of Geosciences, Utrecht University, Princetonlaan 8a, 3584 CB Utrecht, Netherlands;3. Section Ecological Chemistry, Alfred Wegener Institut-Helmholtz Zentrum für Polar- und Meeresforschung (AWI), Am Handelshafen 12, 27570 Bremerhaven, Germany;4. Section Shelf Sea System Ecology, Alfred Wegener Institut-Helmholtz Zentrum für Polar- und Meeresforschung (AWI), Biologische Anstalt Helgoland (BAH), Kurpromenade 201, 27498 Helgoland, Germany;5. Department of Microbial Ecology, Netherlands Institute of Ecology (NIOO-KNAW), Droevendaalsesteeg 10, 6708PB Wageningen, Netherlands;1. Actelion Pharmaceuticals Ltd, Part of Janssen Pharmaceutical Companies of Johnson & Johnson, Allschwil, Switzerland;2. Certara, Inc, San Diego, CA, USA;3. Janssen Research & Development, LLC, Spring House, USA |
| |
| Abstract: | This paper presents distributed algorithms for some graph problems on a network model of computation. These graph problems include breadth-first and breadth-depth searches of graphs, recognition of directed acyclic graphs and strong connectedness, finding weights of all the shortest paths from a single source to all other nodes in a weighted directed acyclic graph, and analyzing activity networks. The results of computations (i.e., the outputs) of all the algorithms but the algorithm for recognition of directed acyclic graphs are available in a distributed manner. For algorithms in such a computational model, two types of complexity measures are important. One is the time complexity and the other is the message or communication complexity. Both of these complexities are obtained for each of the aforesaid distributed algorithms. |
| |
| Keywords: | |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
