Timeline for When can I be sure a directed graph is acyclic?
Current License: CC BY-SA 3.0
5 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Nov 12, 2011 at 20:30 | comment | added | Daniel Scocco | @kevin cline, I mean to verify the cyclyes analyzing the adjacency matrix only, so this would be n^2 (you basically need to traverse the matrix n x n (where n is the number of vertices). If you use a better algorithm then yeah the complexity will probably be O(V+E). | |
| Nov 12, 2011 at 15:43 | comment | added | kevin cline | @Daniel: Definitely not n^2. More like O(n + e). | |
| Nov 12, 2011 at 13:04 | vote | accept | Daniel Scocco | ||
| Nov 12, 2011 at 13:00 | comment | added | Daniel Scocco | Gotcha. And yeah to verify those on large/complex graphs the cost would be (n^2) if I am not wrong (you basically would need to traverse the adjacency matrix). But for simple ones it might be a good idea. Thanks for the answer. | |
| Nov 12, 2011 at 12:56 | history | answered | thiton | CC BY-SA 3.0 |