A universal concept for robust solving of shortest path problems in dynamically reconfigurable graphs
type: Item
instance of: scholarly article
title: A universal concept for robust solving of shortest path problems in dynamically reconfigurable graphs
zbMATH Open document ID: 1394.68264
DOI: 10.1155/2015/345049
author: J. C. Chedjou
author: K. Kyamakya
published in: Mathematical Problems in Engineering
publication date: 2018-08-27T00:00:00Z
review text: Summary: This paper develops a flexible analytical concept for robust shortest path detection in dynamically reconfigurable graphs. The concept is expressed by a mathematical model representing the shortest path problem solver. The proposed mathematical model is characterized by three fundamental parameters expressing (a) the graph topology (through the ``incidence matrix''), (b) the edge weights (with dynamic external weights' setting capability), and (c) the dynamic reconfigurability through external input(s) of the source-destination nodes pair. In order to demonstrate the universality of the developed concept, a general algorithm is proposed to determine the three fundamental parameters (of the mathematical model developed) for all types of graphs regardless of their topology, magnitude, and size. It is demonstrated that the main advantage of the developed concept is that arc costs, the origin-destination pair setting, and the graph topology are dynamically provided by external commands, which are inputs of the shortest path solver model. This enables high flexibility and full reconfigurability of the developed concept, without any retraining need. To validate the concept developed, benchmarking is performed leading to a comparison of its performance with the performances of two well-known concepts based on neural networks.
Mathematics Subject Classification ID: 68R10
Mathematics Subject Classification ID: 05C38
Mathematics Subject Classification ID: 05C85
Mathematics Subject Classification ID: 68T20
Mathematics Subject Classification ID: 90C35
zbMATH DE Number: 6926098
describes a project that uses: MAXFLOW
describes a project that uses: JADE
MaRDI profile type: Publication
full work available at URL: https://doi.org/10.1155/2015/345049
OpenAlex ID: W2202860482
Wikidata QID: Q59118081
cites work: On the Shortest Path Through a Number of Points
cites work: Three-stage approaches for optimizing some variations of the resource constrained shortest-path sub-problem in a column generation context
cites work: Encyclopedia of Algorithms
cites work: Finding the most vital node of a shortest path.
cites work: Q3241581
cites work: A note on two problems in connexion with graphs
cites work: On a routing problem
cites work: Q3292914
cites work: Heuristic shortest path algorithms for transportation applications: state of the art
cites work: Algorithms – ESA 2004
cites work: Scaling Algorithms for the Shortest Paths Problem
cites work: All pairs shortest paths using bridging sets and rectangular matrix multiplication
cites work: A new approach to all-pairs shortest paths on real-weighted graphs
cites work: Undirected single-source shortest paths with positive integer weights in linear time
cites work: UTILIZING DISTRIBUTED LEARNING AUTOMATA TO SOLVE STOCHASTIC SHORTEST PATH PROBLEMS
cites work: Improved calculation method of shortest path with cellular automata model
cites work: ``Neural'' computation of decisions in optimization problems
cites work: A review of Hopfield neural networks for solving mathematical programming problems
description: scientific article; zbMATH DE number 6926098