Timeline for Determine whether there exists a path in a directed acyclic graph that reaches all nodes without revisiting a node
Current License: CC BY-SA 4.0
11 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Mar 4, 2020 at 11:02 | history | bumped | CommunityBot | This question has answers that may be good or bad; the system has marked it active so that they can be reviewed. | |
| Feb 10, 2020 at 13:34 | comment | added | John L. | @MiteshKumar Is my answer helpful? Do you need more details? (This comment will be deleted.) | |
| Feb 3, 2020 at 10:59 | history | edited | John L. | CC BY-SA 4.0 |
copy-edit
|
| Feb 3, 2020 at 10:29 | answer | added | John L. | timeline score: 2 | |
| Feb 2, 2020 at 20:17 | comment | added | Joshua Anderson | Look at the title. I am only considering DAGS. No cycles, and only directed links. | |
| Feb 2, 2020 at 6:15 | comment | added | Yuval Filmus | I don't understand your problem. If your graph isn't a directed path, there is no directed path that visits all vertices. | |
| Feb 2, 2020 at 2:41 | comment | added | Joshua Anderson | Yes, I am saying its O(n) because I don't recalculate the values If its a node that I already visited. It is not 2^n... | |
| Feb 2, 2020 at 2:04 | comment | added | Antti Röyskö | "A little less"? Your algorithm has runtime $\mathcal{O}(2^{n})$ in a complete graph, unless you memoize the values DFS_find(Node), in which case the complexity of both algorithms is linear. | |
| Feb 2, 2020 at 1:21 | history | edited | Joshua Anderson | CC BY-SA 4.0 |
added 172 characters in body
|
| Feb 2, 2020 at 1:20 | review | First posts | |||
| Feb 2, 2020 at 2:06 | |||||
| Feb 2, 2020 at 1:15 | history | asked | Joshua Anderson | CC BY-SA 4.0 |