#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 | Keywords:
Merged in: | Authors:
Reviewers: | Report Upstream: N/A
Work issues: | Branch:
Commit: | Dependencies:
Stopgaps: |
----------------------------+----------------------------
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 colours.
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 colour
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 G, when restricted to any V^i^.
--
Ticket URL: <http://trac.sagemath.org/ticket/17188>
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.
