What are graph algorithms that benefit (in their time complexity) from using the Adjacency Matrix?
$begingroup$
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!
graph-theory graph-connectivity
asked Dec 6 '18 at 21:14
MacMac
162
$endgroup$
add a comment |
$begingroup$
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!
graph-theory graph-connectivity
asked Dec 6 '18 at 21:14
MacMac
162
$endgroup$
$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
add a comment |
$begingroup$
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!
graph-theory graph-connectivity
asked Dec 6 '18 at 21:14
MacMac
162
$endgroup$
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!
graph-theory graph-connectivity
graph-theory graph-connectivity
asked Dec 6 '18 at 21:14
MacMac
162
asked Dec 6 '18 at 21:14
MacMac
162
edited Dec 6 '18 at 22:07
Mac
asked Dec 6 '18 at 21:14
MacMac
162
asked Dec 6 '18 at 21:14
MacMac
162
asked Dec 6 '18 at 21:14
MacMac
162
162
$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
add a comment |
$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
$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
$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
add a comment |
0
active
oldest
votes
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "69"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3029058%2fwhat-are-graph-algorithms-that-benefit-in-their-time-complexity-from-using-the%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
0
active
oldest
votes
0
active
oldest
votes
active
oldest
votes
active
oldest
votes
Thanks for contributing an answer to Mathematics Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3029058%2fwhat-are-graph-algorithms-that-benefit-in-their-time-complexity-from-using-the%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
$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