DSpace Repository

Improvement of shortest-path algorithms using subgraphs heuristics

Show simple item record

dc.contributor.author Khamayseh, Faisal
dc.contributor.author Arman, Nabil
dc.date.accessioned 2017-01-17T11:57:31Z
dc.date.accessioned 2022-05-22T08:26:37Z
dc.date.available 2017-01-17T11:57:31Z
dc.date.available 2022-05-22T08:26:37Z
dc.date.issued 2015-06-10
dc.identifier.citation 2 en_US
dc.identifier.issn 1817-3195
dc.identifier.uri http://localhost:8080/xmlui/handle/123456789/7770
dc.description.abstract Given a graph G=(V,E,w), where V and E are finite set of vertices and edges respectively, is a directed weighted graph with weights denoted by w(e)>0 for each edge e ∈E. P(s,t) is the shortest path between the given vertices <s> and <t> containing the least sum of edge weights on the path from <s> to <t>. Properties of the graph representation, using different matrix structures to represent the graph in normal flow and reverse representations, are considered. Based on these structures, a new algorithm determines the candidate subgraphs and prunes every subgraph that is either unreachable from the given source vertex <s> or does not lead to the given destination<t>, benefiting from the rich information inherent in the matrix and reverse matrix structure representations of the graph. The experiments were conducted using our heuristic and the conventional shortest path finding, namely Dijkstra’s algorithm. Practical results are given showing considerable improvements of the proposed algorithm in performance. This improves the shortest path algorithm significantly. Improvement of shortest-path algorithms using subgraphs heuristics. Available from: https://www.researchgate.net/publication/281061037_Improvement_of_shortest-path_algorithms_using_subgraphs_heuristics [accessed Jan 17, 2017]. en_US
dc.description.sponsorship The Scientific Research Council, Ministry of Education and Higher Education, State of Palestine under a project number of 01/12/2013, and Palestine Polytechnic University. en_US
dc.language.iso en_US en_US
dc.publisher Journal of Theoretical and Applied Information Technology en_US
dc.subject Shortest Path, Pruning, Graph Algorithms, Candidate Subgraphs, Heuristics en_US
dc.title Improvement of shortest-path algorithms using subgraphs heuristics en_US
dc.type Article en_US

Files in this item

This item appears in the following Collection(s)

Show simple item record

Search DSpace


My Account