Timeline for Are regular graphs the hardest instance for graph isomorphism?
Current License: CC BY-SA 3.0
6 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Oct 5, 2017 at 1:17 | history | edited | Timothy Chow | CC BY-SA 3.0 |
corrected reference
|
| Oct 5, 2017 at 1:16 | comment | added | Timothy Chow | @JoshuaGrochow : Good catch! I originally had in mind Deo and Tener, "Attacks on hard instances of graph isomorphism," Journal of Combinatorial Mathematics and Combinatorial Computing 64:203–226, February 2008. I guess I was careless in my copying and pasting. But looking again now, I see that maybe Tener's thesis is the more readily available document after all. I will edit. | |
| Oct 4, 2017 at 19:05 | comment | added | Joshua Grochow | @TimothyChow: Great answer! The current link is to Tener's PhD thesis, supervised by Deo. Is that what you meant to link to (in which case it should probably just be "Tener"), or is there another paper by the two of them you meant to point to? | |
| Sep 17, 2017 at 7:52 | comment | added | Brendan McKay | Incidentally, the Johnson graphs that play a key role in Babai's algorithm are actually quite easy for "nauty" and also for "Traces", "bliss", etc.. That is because those algorithms utilise automorphisms in an efficient way. | |
| Sep 16, 2017 at 23:43 | comment | added | Joseph O'Rourke | Informative answer: "we still don't fully understand what the 'hardest cases' of graph isomorphism are." | |
| Sep 16, 2017 at 23:26 | history | answered | Timothy Chow | CC BY-SA 3.0 |