Timeline for Canonical permutation of a symmetric matrix
Current License: CC BY-SA 4.0
7 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Apr 11, 2021 at 6:43 | vote | accept | mikado | ||
| Apr 7, 2021 at 15:12 | comment | added | Daniel Lichtblau | (1) I was wondering if you had intended subgraph rather than graph. (2) I imagine you are right about such optimizations though I do not know for certain. | |
| Apr 7, 2021 at 7:33 | comment | added | Fidel I. Schaposnik |
@DanielLichtblau Sorry, I mixed it up with the subgraph isomorphism problem also mentioned in the Wikipedia page, I've now edited my answer to avoid confusion. In any case, I expect optimizations such as the one you suggest are already implemented by CanonicalGraph
|
|
| Apr 6, 2021 at 17:21 | history | edited | Fidel I. Schaposnik | CC BY-SA 4.0 |
added 51 characters in body
|
| Apr 5, 2021 at 13:40 | comment | added | Daniel Lichtblau | I think there is an optimization that could reduce complexity of this method. Step 1: Take any permutation that moves all 1's ir now 1 as far right as possible. Apply it both to rows and columns. Step 2: We now have row 1 as 0,...,0,1,...,1, that is, a block of 0s and a block of 1s. Within each block, take an permutation that moves 1s in row 2 as far to the right as possible. Apply it to rows and columns. We now have four blocks. Repeat block-wise on row 3, etc. I suspect the worst-case complexity will be due to the permutation matrix multiplications. | |
| Apr 5, 2021 at 13:28 | comment | added | Daniel Lichtblau | I don't think complexity of graph isomorphism is known to be NP-complete (or NP-anything, for that matter). This is still a reasonable answer though. | |
| Apr 5, 2021 at 7:41 | history | answered | Fidel I. Schaposnik | CC BY-SA 4.0 |