Timeline for Minimum spanning tree of multi directed graph
Current License: CC BY-SA 4.0
14 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Sep 30, 2020 at 6:27 | vote | accept | Edward | ||
| Sep 30, 2020 at 6:27 | comment | added | Edward | Thanks for reminding me. Have posted an answer. But I think it's better to have the title corrected. | |
| Sep 30, 2020 at 6:22 | answer | added | Edward | timeline score: 0 | |
| Sep 30, 2020 at 6:22 | history | edited | Edward | CC BY-SA 4.0 |
deleted 143 characters in body
|
| Sep 29, 2020 at 19:19 | comment | added | D.W.♦ | We operate differently than discussion forums you might be used to. Please don't edit the question to add "SOLVED" to it. Instead, write your own answer that describes the solution in detail, in the 'Your Answer' box below. | |
| Sep 29, 2020 at 18:00 | history | edited | Edward | CC BY-SA 4.0 |
emphasise that the question has been identified
|
| Aug 25, 2020 at 18:03 | comment | added | Edward |
Thanks for the quick reply. I think we are talking about the same thing. As for the min-cost arborescence algorithm you mentioned, I found minimum_spanning_arborescence in networkx works for directed multi-graph. It works for this example. I saw the authors are discussing it as well in #3825.
|
|
| Aug 25, 2020 at 17:56 | comment | added | Edward | I know the direction according to other information. The resulted rooted tree should not violate these information. | |
| Aug 25, 2020 at 17:51 | comment | added | Edward |
After the "if they are chosen" part, I missed a not.
|
|
| Aug 25, 2020 at 17:45 | history | edited | Edward | CC BY-SA 4.0 |
I missed "not"
|
| Aug 25, 2020 at 17:27 | comment | added | BearAqua the Logician | Also, by "if they are chosen" do you mean once we decide to include the edge in the algorithm, its direction will "magically" be specified via an oracle? If that's the case then we can just trivially query for all edges' directions first in $O(|E|)$-time and then use the min-cost arboresence algorithm. | |
| Aug 25, 2020 at 17:25 | comment | added | BearAqua the Logician | Can you please clarify your problem? I'm not sure I understand the problem you described in the first part of your question, and how it relates to the definition of an oriented spanning tree in the second part of your question. IIRC the definition of a directed multigraph usually has the undirected edges represent two connected edges in opposite directions. Is that the case here? In this case, I'm almost certain what you want is exactly the min-cost arborescence algorithm. | |
| Aug 25, 2020 at 17:19 | history | edited | Edward | CC BY-SA 4.0 |
To make the title shorter
|
| Aug 25, 2020 at 17:13 | history | asked | Edward | CC BY-SA 4.0 |