Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2410.18772 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866908765692887040 |
|---|---|
| author | Melent'ev, V. A. |
| author_facet | Melent'ev, V. A. |
| contents | The search is based on the preliminary transformation of matrices or adjacency lists traditionally used in the study of graphs into projections cleared of redundant information (refined) followed by the selection of the desired shortest paths. Each projection contains complete information about all the shortest paths from its base (angle vertex) and is based on an enumeration of reachability relations, more complex than the traditionally used binary adjacency relations. The class of graphs considered was expanded to mixed graphs containing both undirected and oriented edges (arcs). A method for representing graph projections in computer memory and finding shortest paths using them is proposed. The reduction in algorithmic complexity achieved, at the same time, will allow the proposed method to be used in information network applications, scientific and technical, transport and logistics, and economic fields. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2410_18772 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Search for shortest paths based on a projective description of unweighted graphs Melent'ev, V. A. Distributed, Parallel, and Cluster Computing The search is based on the preliminary transformation of matrices or adjacency lists traditionally used in the study of graphs into projections cleared of redundant information (refined) followed by the selection of the desired shortest paths. Each projection contains complete information about all the shortest paths from its base (angle vertex) and is based on an enumeration of reachability relations, more complex than the traditionally used binary adjacency relations. The class of graphs considered was expanded to mixed graphs containing both undirected and oriented edges (arcs). A method for representing graph projections in computer memory and finding shortest paths using them is proposed. The reduction in algorithmic complexity achieved, at the same time, will allow the proposed method to be used in information network applications, scientific and technical, transport and logistics, and economic fields. |
| title | Search for shortest paths based on a projective description of unweighted graphs |
| topic | Distributed, Parallel, and Cluster Computing |
| url | https://arxiv.org/abs/2410.18772 |