Timeline for Lexicographically largest incidence matrix
Current License: CC BY-SA 4.0
10 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jul 27 at 9:18 | comment | added | Ihromant | @fedja yes, It's according to reading like a page in a book. You "read" two incidence matrices of same size left to right, top to bottom until you find 1 in one position and 0 in second. Then first matrix is lexicographically bigger. In example above "output" is bigger due to 1 on 3rd position in "output" and 0 on 3rd position in "input". | |
| Jul 27 at 2:42 | comment | added | fedja | Could you, please, remind us what is the lexicographic order on $m\times n$ $0-1$ matrices? Is it according to reading left to right top to bottom like a page in a book, or something else? | |
| Jul 20 at 10:17 | comment | added | joro | I am permuting for a toy implementation. The problem can be formulated to integer program, which is faster than permuting, but still of exponential complexity. | |
| Jul 20 at 10:08 | comment | added | Ihromant | It could be related. Still, while looked at your code I spotted that you are iterating over permutations(n). If n>10 it leads to unacceptable running time. Still, nauty runs pretty fast on non-regular graph. I assume that there is (or could be) algorithm which runs with approximately similar time. | |
| Jul 20 at 9:55 | comment | added | joro | Is this related to Complete graph invariant based on integer programming? | |
| Jul 20 at 9:53 | comment | added | Ihromant | @DanielWeber Yes, I understand that. Still, graph canonical form (I reimplemented nauty's approach from arxiv.org/abs/1301.1493 Practical graph isomorphism) produces not lexicographically largest incidence matrix. | |
| Jul 20 at 2:29 | comment | added | Daniel Weber | This is similar to lexicographically smallest graph canonization, which is known to be NP-hard, but for bipartite graphs. I think there's a good chance it's NP-hard as well | |
| S Jul 20 at 1:35 | history | suggested | J. W. Tanner | CC BY-SA 4.0 |
Corrected spelling in the title
|
| Jul 19 at 23:27 | review | Suggested edits | |||
| S Jul 20 at 1:35 | |||||
| Jul 19 at 22:25 | history | asked | Ihromant | CC BY-SA 4.0 |