Adjacency Maps and Efficient Graph Algorithms
Graph algorithms that test adjacencies are usually implemented with an adjacency-matrix representation because the adjacency test takes constant time with adjacency matrices, but it takes linear time in the degree of the vertices with adjacency lists. In this article, we review the adjacency-map rep...
| Main Author: | |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2022-02-01
|
| Series: | Algorithms |
| Subjects: | |
| Online Access: | https://www.mdpi.com/1999-4893/15/2/67 |
| _version_ | 1797483522462580736 |
|---|---|
| author | Gabriel Valiente |
| author_facet | Gabriel Valiente |
| author_sort | Gabriel Valiente |
| collection | DOAJ |
| description | Graph algorithms that test adjacencies are usually implemented with an adjacency-matrix representation because the adjacency test takes constant time with adjacency matrices, but it takes linear time in the degree of the vertices with adjacency lists. In this article, we review the adjacency-map representation, which supports adjacency tests in constant expected time, and we show that graph algorithms run faster with adjacency maps than with adjacency lists by a small constant factor if they do not test adjacencies and by one or two orders of magnitude if they perform adjacency tests. |
| first_indexed | 2024-03-09T22:48:16Z |
| format | Article |
| id | doaj.art-3d736d40ff8f409ab058bbfc682b3ab7 |
| institution | Directory Open Access Journal |
| issn | 1999-4893 |
| language | English |
| last_indexed | 2024-03-09T22:48:16Z |
| publishDate | 2022-02-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Algorithms |
| spelling | doaj.art-3d736d40ff8f409ab058bbfc682b3ab72023-11-23T18:24:30ZengMDPI AGAlgorithms1999-48932022-02-011526710.3390/a15020067Adjacency Maps and Efficient Graph AlgorithmsGabriel Valiente0Department of Computer Science, Technical University of Catalonia, E-08034 Barcelona, SpainGraph algorithms that test adjacencies are usually implemented with an adjacency-matrix representation because the adjacency test takes constant time with adjacency matrices, but it takes linear time in the degree of the vertices with adjacency lists. In this article, we review the adjacency-map representation, which supports adjacency tests in constant expected time, and we show that graph algorithms run faster with adjacency maps than with adjacency lists by a small constant factor if they do not test adjacencies and by one or two orders of magnitude if they perform adjacency tests.https://www.mdpi.com/1999-4893/15/2/67discrete mathematicsgraph theoryperformance and testing of algorithmsadjacency matricesadjacency listsadjacency maps |
| spellingShingle | Gabriel Valiente Adjacency Maps and Efficient Graph Algorithms Algorithms discrete mathematics graph theory performance and testing of algorithms adjacency matrices adjacency lists adjacency maps |
| title | Adjacency Maps and Efficient Graph Algorithms |
| title_full | Adjacency Maps and Efficient Graph Algorithms |
| title_fullStr | Adjacency Maps and Efficient Graph Algorithms |
| title_full_unstemmed | Adjacency Maps and Efficient Graph Algorithms |
| title_short | Adjacency Maps and Efficient Graph Algorithms |
| title_sort | adjacency maps and efficient graph algorithms |
| topic | discrete mathematics graph theory performance and testing of algorithms adjacency matrices adjacency lists adjacency maps |
| url | https://www.mdpi.com/1999-4893/15/2/67 |
| work_keys_str_mv | AT gabrielvaliente adjacencymapsandefficientgraphalgorithms |