Re: C-equivalence aware hash function

daw@xxxxxxxxxxxxxxxxxxxxxxxx (David Wagner) wrote:

> Can we view the nxn matrix M as the adjacency matrix of a bipartite
> graph G(M) on 2n vertices? Number the vertices on the left side 1..n,
> and the vertices on the right side n+1..2n. If M_ij = 1, then there
> is an undirected edge between vertex i and vertex n+j. Otherwise,
> there is no such edge. Row swaps correspond to swapping labels on
> two vertices on the left side. Column swaps correspond to swapping
> labels on two vertices on the right side. If we can get from M to M'
> by row and column swaps, then I think we can get from G(M) to G(M')
> by relabelling vertices, and vice versa.

Things get so easy when David explain them...

In my case the matrix is not square, but the analogy still holds.
+1/-1 can be represented by colored or directed edges; and polarity swap
of colum by changing color or direction of all edges attaches to a column.

Thus my problem seems a (harder) variant of graph isomorphism, and probably
similar techniques apply.

Thanks all..

François Grieu
.

Relevant Pages

  • Re: C-equivalence aware hash function
    ... >> problem of graph isomorphism. ... Row swaps correspond to swapping labels on ... by row and column swaps, then I think we can get from Gto G ...
    (sci.crypt)
  • Re: C-equivalence aware hash function
    ... > daw@xxxxxxxxxxxxxxxxxxxxxxxx (David Wagner) wrote: ... >> Can we view the nxn matrix M as the adjacency matrix of a bipartite ... >> graph Gon 2n vertices? ... The paper about Nauty in fact describes "Hadamard equivalence" on p. ...
    (sci.crypt)