About an algorithm to find a maximal vertex-disjoint (except for endpoints) set of paths from $s$ to $t$ in...
I am reading "An $n^{frac{5}{2}}$ Algorithm for Maximum Matchings in Bipartite Graphs" by Hopcroft and Karp. In this paper, the authors wrote an algorithm to find a maximal vertex-disjoint (except for endpoints) set of paths from $s$ to $t$ in an arbitrary acyclic directed graph $H$.
I wonder this algorithm works for an arbitrary directed graph instead of an arbitrary acyclic directed graph.
My 1st Question:
Is there a cyclic directed graph for which this algorithm doesn't work?
My 2nd Question:
There is not the operator $mathrm{DELETE}$ in Algorithm B below.
I guess the right place to write "$mathrm{DELETE}$" is the place immediate after "$mathrm{FIRST} = $ first element of $mathrm{LIST(TOP)}$".
Am I right or wrong?
The following is the algorithm:
We assume that the graph is represented as follows: for each vertex $u$, a read-only linear list $mathrm{LIST}(u)$ is given containing, in an arbitrary order, the vertices $v$ such that $(u, v)$ is an edge. The algorithm also uses an auxiliary last-in first-out list called $mathrm{STACK}$, which is initially empty, and a set $B$ of vertices which is initially the empty set. The following primitives occur in the algorithm.
graph-theory algorithms searching
asked Nov 25 '18 at 9:19
tchappy ha
405210
add a comment |
I am reading "An $n^{frac{5}{2}}$ Algorithm for Maximum Matchings in Bipartite Graphs" by Hopcroft and Karp. In this paper, the authors wrote an algorithm to find a maximal vertex-disjoint (except for endpoints) set of paths from $s$ to $t$ in an arbitrary acyclic directed graph $H$.
I wonder this algorithm works for an arbitrary directed graph instead of an arbitrary acyclic directed graph.
My 1st Question:
Is there a cyclic directed graph for which this algorithm doesn't work?
My 2nd Question:
There is not the operator $mathrm{DELETE}$ in Algorithm B below.
I guess the right place to write "$mathrm{DELETE}$" is the place immediate after "$mathrm{FIRST} = $ first element of $mathrm{LIST(TOP)}$".
Am I right or wrong?
The following is the algorithm:
We assume that the graph is represented as follows: for each vertex $u$, a read-only linear list $mathrm{LIST}(u)$ is given containing, in an arbitrary order, the vertices $v$ such that $(u, v)$ is an edge. The algorithm also uses an auxiliary last-in first-out list called $mathrm{STACK}$, which is initially empty, and a set $B$ of vertices which is initially the empty set. The following primitives occur in the algorithm.
graph-theory algorithms searching
asked Nov 25 '18 at 9:19
tchappy ha
405210
add a comment |
I am reading "An $n^{frac{5}{2}}$ Algorithm for Maximum Matchings in Bipartite Graphs" by Hopcroft and Karp. In this paper, the authors wrote an algorithm to find a maximal vertex-disjoint (except for endpoints) set of paths from $s$ to $t$ in an arbitrary acyclic directed graph $H$.
I wonder this algorithm works for an arbitrary directed graph instead of an arbitrary acyclic directed graph.
My 1st Question:
Is there a cyclic directed graph for which this algorithm doesn't work?
My 2nd Question:
There is not the operator $mathrm{DELETE}$ in Algorithm B below.
I guess the right place to write "$mathrm{DELETE}$" is the place immediate after "$mathrm{FIRST} = $ first element of $mathrm{LIST(TOP)}$".
Am I right or wrong?
The following is the algorithm:
We assume that the graph is represented as follows: for each vertex $u$, a read-only linear list $mathrm{LIST}(u)$ is given containing, in an arbitrary order, the vertices $v$ such that $(u, v)$ is an edge. The algorithm also uses an auxiliary last-in first-out list called $mathrm{STACK}$, which is initially empty, and a set $B$ of vertices which is initially the empty set. The following primitives occur in the algorithm.
graph-theory algorithms searching
asked Nov 25 '18 at 9:19
tchappy ha
405210
I am reading "An $n^{frac{5}{2}}$ Algorithm for Maximum Matchings in Bipartite Graphs" by Hopcroft and Karp. In this paper, the authors wrote an algorithm to find a maximal vertex-disjoint (except for endpoints) set of paths from $s$ to $t$ in an arbitrary acyclic directed graph $H$.
I wonder this algorithm works for an arbitrary directed graph instead of an arbitrary acyclic directed graph.
My 1st Question:
Is there a cyclic directed graph for which this algorithm doesn't work?
My 2nd Question:
There is not the operator $mathrm{DELETE}$ in Algorithm B below.
I guess the right place to write "$mathrm{DELETE}$" is the place immediate after "$mathrm{FIRST} = $ first element of $mathrm{LIST(TOP)}$".
Am I right or wrong?
The following is the algorithm:
We assume that the graph is represented as follows: for each vertex $u$, a read-only linear list $mathrm{LIST}(u)$ is given containing, in an arbitrary order, the vertices $v$ such that $(u, v)$ is an edge. The algorithm also uses an auxiliary last-in first-out list called $mathrm{STACK}$, which is initially empty, and a set $B$ of vertices which is initially the empty set. The following primitives occur in the algorithm.
graph-theory algorithms searching
graph-theory algorithms searching
asked Nov 25 '18 at 9:19
tchappy ha
405210
asked Nov 25 '18 at 9:19
tchappy ha
405210
asked Nov 25 '18 at 9:19
tchappy ha
405210
asked Nov 25 '18 at 9:19
tchappy ha
405210
asked Nov 25 '18 at 9:19
tchappy ha
405210
405210
add a comment |
add a comment |
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%2f3012613%2fabout-an-algorithm-to-find-a-maximal-vertex-disjoint-except-for-endpoints-set%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
active
oldest
votes
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.
Some of your past answers have not been well-received, and you're in danger of being blocked from answering.
Please pay close attention to the following guidance:
- 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.
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%2f3012613%2fabout-an-algorithm-to-find-a-maximal-vertex-disjoint-except-for-endpoints-set%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
