Timeline for Finding a cycle of fixed length
Current License: CC BY-SA 2.5
8 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jul 24, 2016 at 1:53 | comment | added | crackpotHouseplant | At first I wondered why you insulted Ryan Williams... | |
| Nov 5, 2013 at 9:33 | comment | added | Ryan Williams | Not sure what you're asking. There can be $\Omega(n^4)$ cycles of length 4 in a graph, so $O(n^4)$ time is the best you can hope for asymptotically if you want to list all 4-cycles. If you're asking how to get the above algorithm to produce a 4-cycle in $O(n^2)$ time when one exists, that's also pretty obvious... | |
| Nov 5, 2013 at 1:10 | comment | added | Nicu Stiurca | Good stuff. How can I detect every cycle of length 4 though? The algorithms you reference seem to only tell you if such a cycle exists or not. | |
| Mar 2, 2010 at 6:11 | comment | added | Ryan Williams | Rune is absolutely right; the random ordering algorithm runs in O(k! (m + n)) time. | |
| Mar 1, 2010 at 23:59 | comment | added | Rune | A linear time algorithm (i.e., O(m+n)) for detecting paths of length k was mentioned in one of Alon et al.'s papers. It just involves choosing a random ordering of the vertices, and making the graph a DAG using this ordering. Since longest path on DAGs can be solved in linear time, a directed path of length k can be found in linear time, if the chosen random ordering works. Repeat the previous step exponentially many times (in k), to get desired randomized algorithm. | |
| Feb 26, 2010 at 7:27 | vote | accept | Hsien-Chih Chang 張顯之 | ||
| Feb 26, 2010 at 7:20 | comment | added | Hsien-Chih Chang 張顯之 | Thank you for mentioning the result about detecting paths. It's new to me and it is very useful. Thanks!! | |
| Feb 26, 2010 at 1:36 | history | answered | Ryan Williams | CC BY-SA 2.5 |