Re: Q: Graph encoding

From: Mitch Harris (harrisq_at_tcs.inf.tu-dresden.de)
Date: 07/13/04

  • Next message: Kent Paul Dolan: "Re: Can you find anything wrong with this solution to the Halting Problem?" 
    Date: 13 Jul 2004 19:15:25 GMT

    Jim Nastos <nastos@cs.ualberta.ca> wrote:
    >On Tue, 13 Jul 2004, Mok-Kong Shen wrote:
    >
    >> Many thanks for the information. I have an additional question:
    >> If the tree (or graph) is not labeled, is there a good mapping
    >> to a number? I mean, if possible, assigning a unique sequential
    >> number to all unlabeled trees/graphs. Thanks.
    >
    > Sure there is, but it just wouldn't be easy to compute.
    > One way you might want to do it is to take the adjacency matrix
    >of a graph and then permute the row/columns in the way that yields
    >a lexicographically-minimal word when the matrix is written as a
    >word (with top line first, concatenated with the second line, etc...)
    >Of course, your word need only contain the upper-triangle of the
    >adjacency matrix.

    Deciding if a matrix is the least lexicographically is NP-complete (by
    reduction from bandwidth).

    > You can come up with whatever method you like to transform a 0-1
    >string into a number, if you really need a number.
    >
    > (Essentially, this is a way of solving the isomorphism problem on
    >graphs, for which there is no known polytime solution... isomorphism
    >on trees, is polytime solvable as you would already know from the
    >previous post.)

    The above fact does not contradict this, it just means that
    theoretically/asymptotically there are better ways.

    So I'll give yet another plug for nauty, which is a very
    efficient practical software package for testing graph isomorphism.

    Mitch

  • Next message: Kent Paul Dolan: "Re: Can you find anything wrong with this solution to the Halting Problem?"

    Relevant Pages