Timeline for Most efficient way to output a cycle starting from an unordered list of graph vertices
Current License: CC BY-SA 3.0
9 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Feb 12, 2013 at 14:11 | comment | added | Szabolcs | Well, you know what you need ... I thought you wanted to avoid the same node being visited twice, which FindEulerianCycle may not. If you're concerned about performance, measure! | |
| Feb 12, 2013 at 11:10 | comment | added | Roger Harris | I think we can just call "FindEulerianCycle" instead of "FindHamiltonianCycle" if we want to use something that everyone knows has linear time solution (if something like Hierholzer's algorithm is being used) or an "almost linear time" solution... which will depend on the exact implementation. | |
| Feb 11, 2013 at 23:12 | comment | added | Szabolcs | @Roget I don't know how it is implemented, but it makes sense to assume that it is linear complexity (in the number of nodes). There aren't that many ways to traverse a cycle graphs. If you want to make sure, you can measure directly. | |
| Feb 11, 2013 at 22:53 | comment | added | Roger Harris | I think I should be able to make my set of vertices a cycle... Do we know the time complexity for "FindHamiltonianCycle" on a cycle graph? | |
| Feb 11, 2013 at 22:08 | comment | added | Szabolcs |
Note that FindHamiltonianCycle is not necessarily slow ("bad" complexity). It is slow for some input graphs, but it isn't for a cycle graph.
|
|
| Feb 11, 2013 at 22:04 | comment | added | Roger Harris | Right, calling "FindHamiltonianCycle" solves my problem, though I have a special very easy case of what would otherwise by an NP-complete problem. I suppose I could also cut the connections between a pair of vertices $v_i$ and $v_j$ and then run "FindShortestPath". | |
| Feb 11, 2013 at 21:57 | vote | accept | Roger Harris | ||
| Feb 11, 2013 at 19:47 | comment | added | Szabolcs | Please let me know if I misunderstood. | |
| Feb 11, 2013 at 19:45 | history | answered | Szabolcs | CC BY-SA 3.0 |