#17188: improve handling edge weights in computing automorphisms of graphs
--------------------------------+------------------------
Reporter: dimpase | Owner:
Type: enhancement | Status: new
Priority: major | Milestone: sage-6.4
Component: graph theory | Resolution:
Keywords: | Merged in:
Authors: | Reviewers:
Report Upstream: N/A | Work issues:
Branch: | Commit:
Dependencies: | Stopgaps:
--------------------------------+------------------------
Description changed by ncohen:
Old description:
> Presently computing the automorphism group of a graph G on n vertices and
> m edges, with weighted edges, involves reducing this to computing the
> automorphism groups of a vertex-weighted graph on n+m(m-1)/2
> vertices.This is too much if m is big.
>
> There is a much better reduction, using only `$n(1+\lceil\log_2
> M\rceil)$` vertices, with M being the number of different weights.
>
> Assume that each vertex a of G has integer weight d_a (for unweighted
> vertices case, assign the same weight to them all). Then, make
> `$b:=1+\lceil\log_2 M\rceil$` copies V^i^ of vertices of G; each edge
> weight of G is encoded by b bits, as follows: if (a,b) is an edge of G of
> c-th weight (with weights numbered from 1 to M), then take the binary
> expansion `$c_1,...,c_b$` of c, and join a^i^ and b^i^ in V^i^ for all i
> s.t. c_i=1. Futher, join a^i^ and a^j^ by an edge, and assign the weight
> d_a+i to each a^i^, for all i.
>
> The automorphism group of the resulting graph on bn vertices is the
> automorphism group of edge (and vertex)-weighted G, when restricted to
> any V^i^.
New description:
Presently computing the automorphism group of a graph G on n vertices and
m edges, with weighted edges, involves reducing this to computing the
automorphism groups of a vertex-weighted graph on n+m vertices.This is too
much if m is big.
There is a much better reduction, using only `$n(1+\lceil\log_2 M\rceil)$`
vertices, with M being the number of different weights.
Assume that each vertex a of G has integer weight d_a (for unweighted
vertices case, assign the same weight to them all). Then, make
`$b:=1+\lceil\log_2 M\rceil$` copies V^i^ of vertices of G; each edge
weight of G is encoded by b bits, as follows: if (a,b) is an edge of G of
c-th weight (with weights numbered from 1 to M), then take the binary
expansion `$c_1,...,c_b$` of c, and join a^i^ and b^i^ in V^i^ for all i
s.t. c_i=1. Futher, join a^i^ and a^j^ by an edge, and assign the weight
d_a+i to each a^i^, for all i.
The automorphism group of the resulting graph on bn vertices is the
automorphism group of edge (and vertex)-weighted G, when restricted to any
V^i^.
--
--
Ticket URL: <http://trac.sagemath.org/ticket/17188#comment:2>
Sage <http://www.sagemath.org>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica,
and MATLAB
--
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
To post to this group, send email to [email protected].
Visit this group at http://groups.google.com/group/sage-trac.
For more options, visit https://groups.google.com/d/optout.
