A spectral approach to the shortest path problem (Q2020688)
From MaRDI portal
 | This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: A spectral approach to the shortest path problem |
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | A spectral approach to the shortest path problem |
scientific article |
Statements
A spectral approach to the shortest path problem (English)
0 references
24 April 2021
0 references
For a simple, connected graph \(G\) with vertices \(u,v\in V(G)\), a spectral algorithm is constructed for finding a shortest path from \(v\) to \(u\) in which the Laplacian matrix is used. The efficiency of this method is due to a discrete analogue of a not well understood phenomenon in partial differential equations. Moreover, the optimality of this method is proved for trees, and some open problems are discussed.
0 references
shortest path problem
0 references
spectral theory
0 references
hot spots
0 references
0 references
0 references
0 references
0 references
0 references
0 references
0.7284880876541138
0 references
0.722905695438385
0 references
0.7093884348869324
0 references
0.708629310131073
0 references
