𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Shortest paths in fuzzy weighted graphs

✍ Scribed by Chris Cornelis; Peter De Kesel; Etienne E. Kerre

Publisher
John Wiley and Sons
Year
2004
Tongue
English
Weight
232 KB
Volume
19
Category
Article
ISSN
0884-8173

No coin nor oath required. For personal study only.

✦ Synopsis

The task of finding shortest paths in weighted graphs is one of the archetypical problems encountered in the domain of combinatorial optimization and has been studied intensively over the past five decades. More recently, fuzzy weighted graphs, along with generalizations of algorithms for finding optimal paths within them, have emerged as an adequate modeling tool for prohibitively complex and/or inherently imprecise systems. We review and formalize these algorithms, paying special attention to the ranking methods used for path comparison. We show which criteria must be met for algorithm correctness and present an efficient method, based on defuzzification of fuzzy weights, for finding optimal paths.

πŸ“œ SIMILAR VOLUMES

Shortest Paths in Distance-regular Graph
Shortest Paths in Distance-regular Graphs
✍ Enrique Bendito; Angeles Carmona; AndrΓ©s M. Encinas πŸ“‚ Article πŸ“… 2000 πŸ› Elsevier Science 🌐 English βš– 150 KB
Faster Shortest-Path Algorithms for Plan
Faster Shortest-Path Algorithms for Planar Graphs
✍ Monika R Henzinger; Philip Klein; Satish Rao; Sairam Subramanian πŸ“‚ Article πŸ“… 1997 πŸ› Elsevier Science 🌐 English βš– 445 KB

We give a linear-time algorithm for single-source shortest paths in planar graphs with nonnegative edge-lengths. Our algorithm also yields a linear-time algorithm for maximum flow in a planar graph with the source and sink on the same face. For the case where negative edge-lengths are allowed, we gi

Path covers of weighted graphs
Path covers of weighted graphs
✍ Genghua Fan πŸ“‚ Article πŸ“… 1995 πŸ› John Wiley and Sons 🌐 English βš– 318 KB

Let (G, w ) denote a simple graph G with a weight function w : €(G) -{0,1,2}. A path cover of (G, w ) is a collection of paths in G such that every edge e is contained in exactly w(e) paths of the collection. For a vertex u , w ( v ) is the sum of the weights of the edges incident with U ; U is call

On the All-Pairs-Shortest-Path Problem i
On the All-Pairs-Shortest-Path Problem in Unweighted Undirected Graphs
✍ R. Seidel πŸ“‚ Article πŸ“… 1995 πŸ› Elsevier Science 🌐 English βš– 318 KB

We present an algorithm, APD, that solves the distance version of the all-pairs-shortest-path problem for undirected, unweighted \(n\)-vertex graphs in time \(O(M(n) \log n)\), where \(M(n)\) denotes the time necessary to multiply two \(n \times n\) matrices of small integers (which is currently kno