I'm trying to understand better the advantages of using the adjacency matrix (AM) graph representation, in the context of time complexity of graph algorithms (I know, AM is quadratic in space, but let's forget space issues in this question).

AM enables checking the existence of an arbitrary edge in a given graph in O(1) time. This is essentially the main asymptotic advantage over the adjacency list/array graph representation (which needs O(log(max-degree)) for checking edge existence, assuming neighbors of each vertex are stored in sorted arrays).

Now, I'm interested in understanding whether this has any real meaning in the context of the time complexity of different graph algorithms. Namely, are there graph algorithms that benefit from this property of the AM, and have better asymptotic behavior when they use AM, instead of the adjacency list/array representation?

(By the way, I know that in various algorithms you can get better time complexity because you manipulate with the AM using linear algebra operations (squaring the matrix, etc.). I do not mean this here. Instead, I'm exclusively interested in what algorithms benefit from the AM ability to verify the existance of an edge in O(1) time).

Thank you!

  • $\begingroup$ @MorganRodgers Thanks for these remarks, I rewrote the whole question to make it more to the point (= why I care). $\endgroup$ – Mac Dec 6 '18 at 21:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.