Timeline for Partitioning graph for Graph Isomorphism [closed]
Current License: CC BY-SA 3.0
22 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Apr 13, 2017 at 12:57 | history | edited | CommunityBot |
replaced http://mathoverflow.net/ with https://mathoverflow.net/
|
|
| S Aug 31, 2015 at 18:22 | history | migration rejected | |||
| S Aug 31, 2015 at 18:22 | history | unlocked | CommunityBot | ||
| S Aug 31, 2015 at 17:41 | history | migrated | Todd Trimble | to cstheory.stackexchange.com | |
| S Aug 31, 2015 at 17:41 | history | locked | CommunityBot | ||
| S Aug 31, 2015 at 17:41 | history | closed | Todd Trimble | Not suitable for this site | |
| Aug 31, 2015 at 17:40 | comment | added | Todd Trimble | Migrating to Theor. Comp. Sci. on request of OP... | |
| Aug 31, 2015 at 17:40 | history | edited | Todd Trimble | CC BY-SA 3.0 |
cleaned up some of the grammar and orthography
|
| Aug 27, 2015 at 3:53 | comment | added | Michael | @BrendanMcKay , The 'Construction' described above can be seen as an individualization technique. Is there any individualization in current literature as describe above in 'Construction' ? Is it actually a k-dimensional Weisfeiler-Lehman method? | |
| Aug 7, 2015 at 18:43 | comment | added | Sebi Cioaba | The strongly regular graph on 416 vertices described in this paper arxiv.org/abs/1305.2584 has a property similar to what is discussed here. | |
| Aug 5, 2015 at 17:25 | history | edited | Michael | CC BY-SA 3.0 |
added 282 characters in body
|
| Aug 1, 2015 at 3:36 | comment | added | Brendan McKay | @Jim, Nobody knows. However it is interesting that the fastest known algorithm for strongly regular graphs is faster than the fastest known for general graphs, see ieeexplore.ieee.org/xpl/… | |
| Aug 1, 2015 at 2:08 | comment | added | Michael | @BrendanMcKay , Sir, you said , that such graphs are not the hardest graphs for the isomorphism problem, can their isomorphism be determined less than quasipolynomial time? | |
| Aug 1, 2015 at 2:05 | comment | added | Brendan McKay | @vzn The existing practical approaches have trouble when there are inequivalent vertices that are hard to distinguish. Regularity is a step in that direction but not enough by itself. On the other hand, very restricted classes of graphs often allow specially tailored treatment. Nobody really knows how to define the "hardest" class of graphs. | |
| Jul 31, 2015 at 23:48 | history | edited | Michael | CC BY-SA 3.0 |
added 44 characters in body
|
| Jul 31, 2015 at 23:24 | comment | added | vzn | @Brendan can you cite something that would point to "the hardest graphs for the isomorphism problem"? arent they thought to be regular? thx! | |
| Jul 31, 2015 at 19:21 | history | edited | Michael | CC BY-SA 3.0 |
deleted 152 characters in body
|
| Jul 29, 2015 at 14:49 | history | edited | Michael |
edited tags
|
|
| Jul 29, 2015 at 9:01 | comment | added | Michael | @BrendanMcKay , Sir, I was/am planing to generalize this class later.For example, Without restriction 2, there will be complete $C_y, D_y$ graphs, complete graphs are not hardest for GI, I guess. | |
| Jul 29, 2015 at 2:52 | comment | added | Brendan McKay | Your conditions indicate that your graph is strongly regular. If C1 and D1 have the same properties, then you have a highly restricted class of strongly regular graphs, see sciencedirect.com/science/article/pii/002186937890220X . It is most unlikely that such graphs are the hardest graphs for the isomorphism problem. | |
| Jul 29, 2015 at 2:04 | history | edited | Michael |
edited tags
|
|
| Jul 29, 2015 at 1:59 | history | asked | Michael | CC BY-SA 3.0 |