An Efficient Algorithm for Enumerating all Minimal Paths of a Graph
Journal Title: International Journal of Advanced Computer Science & Applications - Year 2019, Vol 10, Issue 1
Abstract
The enumeration of all minimal paths between a terminal pair of a given graph is widely used in a lot of applications such as network reliability assessment. In this paper, we present a new and efficient algorithm to generate all minimal paths in a graph G(V, E). The algorithm proposed builds the set of minimal paths gradually, starting from the source nodes. We present two versions of our algorithm; the first version determines all feasible paths between a pair of terminals in a directed graph without cycle, and this version runs in linear time O(|V| + |E|). The second version determines all minimal paths in a general graph (directed and undirected graph). In order to show the process and the effectiveness of our method, an illustrative example is presented for each case.
Authors and Affiliations
Khalid Housni
Keywords
Related Articles
- EP ID EP448908
- DOI 10.14569/IJACSA.2019.0100159
- Views 91
- Downloads 0
Multi-Objective Task Scheduling in Cloud Computing Using an Imperialist Competitive Algorithm
Cloud computing is being welcomed as a new basis to manage and provide services on the internet. One of the reasons for increased efficiency of this environment is the appropriate structure of the tasks scheduler. Since...
Smart Parking Architecture based on Multi Agent System
Finding a parking space in big cities is becoming more and more impossible. In addition, the emergence of car has created several problems relating to urban mobility for the city. But with the development of technology,...
Comprehensive Centralized-Data Warehouse for Managing Malaria Cases
Tanah Bumbu is one of the most endemic areas in Indonesia for patients diagnosed with malaria diseases. Currently, available malaria case data were stored in disparate sources. Hence, it is difficult for the public healt...
OFW-ITS-LSSVM: Weighted Classification by LS-SVM for Diabetes diagnosis
In accordance to the fast developing technology now a days, every field is gaining it’s benefit through machines other than human involvement. Many changes are being made much advancement is possible by this develo...
Proposal of the Support Tool for After-Class Work based on the Online Threaded Bulletin Board
In this paper, based on the assumption that after-class work in an exercise-based course accompanied by group work is done on an online threaded bulletin board system, the authors propose a support tool for the instructo...