< ^ From:

< ^ Subject:

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,

Igor

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]