{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,24]],"date-time":"2025-11-24T16:42:04Z","timestamp":1764002524839,"version":"build-2065373602"},"reference-count":11,"publisher":"MDPI AG","issue":"2","license":[{"start":{"date-parts":[[2022,2,20]],"date-time":"2022-02-20T00:00:00Z","timestamp":1645315200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100003030","name":"Agency for Administration of University and Research","doi-asserted-by":"publisher","award":["2017-SGR-786"],"award-info":[{"award-number":["2017-SGR-786"]}],"id":[{"id":"10.13039\/501100003030","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>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.<\/jats:p>","DOI":"10.3390\/a15020067","type":"journal-article","created":{"date-parts":[[2022,2,21]],"date-time":"2022-02-21T08:14:46Z","timestamp":1645431286000},"page":"67","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Adjacency Maps and Efficient Graph Algorithms"],"prefix":"10.3390","volume":"15","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-9194-2703","authenticated-orcid":false,"given":"Gabriel","family":"Valiente","sequence":"first","affiliation":[{"name":"Department of Computer Science, Technical University of Catalonia, E-08034 Barcelona, Spain"}]}],"member":"1968","published-online":{"date-parts":[[2022,2,20]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"9","DOI":"10.1016\/j.ipl.2004.06.002","article-title":"Trading uninitialized space for time","volume":"92","author":"Valiente","year":"2004","journal-title":"Inf. Process. Lett."},{"key":"ref_2","unstructured":"Cormen, T.H., Leiserson, C.E., Rivest, R.L., and Stein, C. (2009). Introduction to Algorithms, MIT Press. [3rd ed.]."},{"key":"ref_3","unstructured":"Mehlhorn, K., and N\u00e4her, S. (1999). The LEDA Platform of Combinatorial and Geometric Computing, Cambridge University Press."},{"key":"ref_4","unstructured":"Siek, J.G., Lee, L.Q., and Lumsdaine, A. (2001). The Boost Graph Library: User Guide and Reference Manual, Addison-Wesley."},{"key":"ref_5","doi-asserted-by":"crossref","unstructured":"Valiente, G. (2021). Algorithms on Trees and Graphs, Springer Nature. [2nd ed.]. Texts in Computer Science.","DOI":"10.1007\/978-3-030-81885-2"},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"146","DOI":"10.1137\/0201010","article-title":"Depth-first search and linear graph algorithms","volume":"1","author":"Tarjan","year":"1972","journal-title":"SIAM J. Comput."},{"key":"ref_7","doi-asserted-by":"crossref","unstructured":"Tarjan, R.E. (1983). Data Structures and Network Algorithms, Society for Industrial and Applied Mathematics.","DOI":"10.1137\/1.9781611970265"},{"key":"ref_8","unstructured":"Goodrich, M.T., Tamassia, R., and Goldwasser, M.H. (2013). Data Structures and Algorithms in Python, John Wiley & Sons, Inc."},{"key":"ref_9","unstructured":"Varoquaux, G., Vaught, T., and Millman, J. (2008, January 19\u201324). Exploring network structure, dynamics, and function using NetworkX. Proceedings of the 7th Python in Science Conference, Pasadena, CA, USA."},{"key":"ref_10","unstructured":"Bollob\u00e1s, B. (2001). Random Graphs, Cambridge University Press. [2nd ed.]. Number 73 in Cambridge Studies in Advanced Mathematics."},{"key":"ref_11","doi-asserted-by":"crossref","unstructured":"Coolen, A.C.C., Annibale, A., and Roberts, E.S. (2017). Generating Random Networks and Graphs, Oxforf University Press.","DOI":"10.1093\/oso\/9780198709893.001.0001"}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/15\/2\/67\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,10]],"date-time":"2025-10-10T22:23:22Z","timestamp":1760135002000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/15\/2\/67"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,2,20]]},"references-count":11,"journal-issue":{"issue":"2","published-online":{"date-parts":[[2022,2]]}},"alternative-id":["a15020067"],"URL":"https:\/\/doi.org\/10.3390\/a15020067","relation":{},"ISSN":["1999-4893"],"issn-type":[{"type":"electronic","value":"1999-4893"}],"subject":[],"published":{"date-parts":[[2022,2,20]]}}}