Re: Cequivalence aware hash function
 From: Francois Grieu <fgrieu@xxxxxxxxxxxx>
 Date: Thu, 01 Dec 2005 22:57:36 +0100
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
.
 FollowUps:
 Re: Cequivalence aware hash function
 From: Milan VXdgsvt
 Re: Cequivalence aware hash function
 References:
 Re: Cequivalence aware hash function
 From: Milan VXdgsvt
 Re: Cequivalence aware hash function
 From: Francois Grieu
 Re: Cequivalence aware hash function
 From: David Wagner
 Re: Cequivalence aware hash function
 Prev by Date: Re: First quantum byte!
 Next by Date: Re: PGP Lame question
 Previous by thread: Re: Cequivalence aware hash function
 Next by thread: Re: Cequivalence aware hash function
 Index(es):
Relevant Pages
