> < ^ Date: Fri, 20 Oct 2000 16:28:18 -0700 (PDT)
< ^ From: Igor Markov <imarkov@cs.ucla.edu >
< ^ Subject: Re: a question on fast symmetry checking

Dear Leonard Soicher,

thank you for the suggestions and the update on the development plans
for GRAPE.

I was wondering if the next versions of GRAPE will be able to
compute automorphisms of sparse hypergraphs (directed or undirected) and
boolean functions in CNF --- in one call each. Both problems can be easily
reduced to the automorphisms of colored graphs (which is what we are doing
now with PERL scripts). Given a boolean function, one can also find its
*semantic* automorphisms (rather than syntactic automorphisms of a CNF, BDD
or some other representation) by computing the automorphisms of the
undirected hypergraph made of the function's truth table (this will
typically require exponentialy large memory, but may take care of some
small yet interesting boolean functions).

>thanks again,

P.S. A marginally related question is whether Graph Automorphism
algorithms (or, more generally, other algorithms of interest
to the GAP audience) can benefit from a min-sum ordering of
vertices of a [hyper]graph. In other words, the objective function
to minimize is the average "span" of an [hyper]edge, where span
is defined as the distance [wrt the ordering] between the first
and the last vertex of this [hyper]edge. I co-wrote a
practically-linear-time approximate solver for this NP-hard problem,
and the C++ code is publically available (distributed under the
MIT / X window license, which permits free use for all purposes).
The algorithm is based on recursive balanced min-cut bisection of
hypergraphs, and our partitioner is one of the best reported in
the literature.

> < [top]