# Computing SODO

N/A
N/A
Protected

Share "Computing SODO"

Copied!
86
0
0

Full text

(1)

### Adolfo Piperno University of Rome

computing sodo — 1

(2)

### Isomorphism and Automorphism

We have some finite objects consisting of some finite sets and some relations on them.

An isomorphism between two objects is a bijection between their sets so that the relations are preserved. Hopefully, isomorphism is an equivalence relation on the set of all objects.

computing sodo — 2

(3)

### Isomorphism and Automorphism

We have some finite objects consisting of some finite sets and some relations on them.

An isomorphism between two objects is a bijection between their sets so that the relations are preserved. Hopefully, isomorphism is an equivalence relation on the set of all objects.

Isomorphisms from an object to itself are automorphisms. If we didn’t do anything silly, the set of automorphisms forms a group under composition.

Of course we call it the automorphism group.

8

1

7 6 5

3 4 2

computing sodo — 2

(4)

### Isomorphism and Automorphism

We have some finite objects consisting of some finite sets and some relations on them.

An isomorphism between two objects is a bijection between their sets so that the relations are preserved. Hopefully, isomorphism is an equivalence relation on the set of all objects.

Isomorphisms from an object to itself are automorphisms. If we didn’t do anything silly, the set of automorphisms forms a group under composition.

Of course we call it the automorphism group.

8

1

7 6 5

3 4 2

(1)

(1 4)(2 3)(5 8)(6 7) (1 8)(2 7)(3 6)(4 5) (1 5)(2 6)(3 7)(4 8)

computing sodo — 2

(5)

### Ubiquity of graph isomorphism

Very many isomorphism problems can be eﬃciently expressed as graph isomorphism problems. For convenience, we usecoloured graphs, in which the vertices (and possibly the edges) are coloured. Isomorphisms must preserve vertex and edge colour.

###  

Say two matrices are isomorphic if one can be obtained from the

other by permuting rows and columns.

computing sodo — 3

(6)

### Ubiquity of graph isomorphism

Very many isomorphism problems can be eﬃciently expressed as graph isomorphism problems. For convenience, we usecoloured graphs, in which the vertices (and possibly the edges) are coloured. Isomorphisms must preserve vertex and edge colour.

= 4

= 5

= 3

= 1

###  

Say two matrices are isomorphic if one can be obtained from the

other by permuting rows and columns.

computing sodo — 3

(7)

###  

Say isomorphism of two ±1 matrices allows permutation and negation of rows and columns.

computing sodo — 4

(8)

###  

Say isomorphism of two ±1 matrices allows permutation and negation of rows and columns.

computing sodo — 4

(9)

###  

Say isomorphism of two matrices allows permutation of rows, columns and symbols.

computing sodo — 5

(10)

1 2

3 1

2

3

1 3 2

###  

Say isomorphism of two matrices allows permutation of rows, columns and symbols.

computing sodo — 5

(11)

1 2

3 1

2

3

1 3 2

1 2

3 1

2

3

1 3 2

###  

Say isomorphism of two matrices allows permutation of rows, columns and symbols.

computing sodo — 5

(12)

1

2

3

1

3

2

2

3

1

3

2

1

### 

computing sodo — 6

(13)

1

2

3

1

3

2

2

3

1

3

2

1

### 

The group elements are edge colours and vertices.

The black vertex is the identity element.

Preserve vertex colours but allow permutation of edge colours.

computing sodo — 6

(14)

1

2

3

1

3

2

2

3

1

3

2

1

### 

The group elements are edge colours and vertices.

The black vertex is the identity element.

Preserve vertex colours but allow permutation of edge colours.

The fastest known algorithm for group isomorphism is trivial and has time

### n

O(logn).

computing sodo — 6

(15)

### 

computing sodo — 7

(16)

###  ?

Suppose isomorphism of two 0-1 matrices means that their columns can be permu- tated so that the rows generate the same vector space over

### GF

(2).

Nobody knows how to make an equivalent graph problem of size which is polynomial in the size of the generator matrix.

computing sodo — 7

(17)

### Isomorphism and automorphism are much the same

computing sodo — 8

(18)

## GH

computing sodo — 8

(19)

## GHHG

computing sodo — 8

(20)

## GHHG

computing sodo — 8

(21)

## GHHG

computing sodo — 8

(22)

## GHHG

computing sodo — 8

(23)

## GHHG

computing sodo — 8

(24)

### Theoretical complexity

The graph isomorphism problem is:

### •

The fastest known algorithm for GI is exp�

(√

log

### n

)�

time; no polynomial time algorithm is known (despite many claims).

### •

GI is not known to be NP-complete.

### •

GI is not known to be in co-NP.

### •

There are polynomial time algorithms for many special classes of graphs (bounded degree, bounded genus, classes with excluded minors or topological subgraphs).

Few of these are practical, planar graphs being a notable exception.

computing sodo — 9

(25)

### Minor-closed classes

computing sodo — 10

(26)

### Minor-closed classes

computing sodo — 10

(27)

4

### as a minor

computing sodo — 10

(28)

4

### as a topological minor

computing sodo — 10

(29)

4

### as a topological minor

Martin Grohe (2012) showed that GI is solvable in polynomial time for any class of graphs that avoid any fixed graph as a topological minor.

computing sodo — 10

(30)

### Problems

1. Prove any of these inequalities are equalities:

### P

≤ Group isomorphism ≤ Graph isomorphism≤ Code isomorphism ≤ NP Graph isomorphism≤ Set-stabiliser in permutation group

computing sodo — 11

(31)

### Problems

1. Prove any of these inequalities are equalities:

### P

≤ Group isomorphism ≤ Graph isomorphism≤ Code isomorphism ≤ NP Graph isomorphism≤ Set-stabiliser in permutation group

2. Improve

### n

O(logn) time for group isomorphism. (Best result so far: polynomial time for groups without abelian normal subgroups: Babai, Codenotte, Gorchow and Qiao, unpublished).

computing sodo — 11

(32)

### Problems

1. Prove any of these inequalities are equalities:

### P

≤ Group isomorphism ≤ Graph isomorphism≤ Code isomorphism ≤ NP Graph isomorphism≤ Set-stabiliser in permutation group

2. Improve

### n

O(logn) time for group isomorphism. (Best result so far: polynomial time for groups without abelian normal subgroups: Babai, Codenotte, Gorchow and Qiao, unpublished).

3. Show that group isomorphism is in co-NP.

computing sodo — 11

(33)

### Problems

1. Prove any of these inequalities are equalities:

### P

≤ Group isomorphism ≤ Graph isomorphism≤ Code isomorphism ≤ NP Graph isomorphism≤ Set-stabiliser in permutation group

2. Improve

### n

O(logn) time for group isomorphism. (Best result so far: polynomial time for groups without abelian normal subgroups: Babai, Codenotte, Gorchow and Qiao, unpublished).

3. Show that group isomorphism is in co-NP.

4. Show that graph isomorphism is in co-NP.

computing sodo — 11

(34)

### Problems

1. Prove any of these inequalities are equalities:

### P

≤ Group isomorphism ≤ Graph isomorphism≤ Code isomorphism ≤ NP Graph isomorphism≤ Set-stabiliser in permutation group

2. Improve

### n

O(logn) time for group isomorphism. (Best result so far: polynomial time for groups without abelian normal subgroups: Babai, Codenotte, Gorchow and Qiao, unpublished).

3. Show that group isomorphism is in co-NP.

4. Show that graph isomorphism is in co-NP.

5. Improve the exp(

(√

log

### n

)) worst case for graph isomorphism.

computing sodo — 11

(35)

### Canonical labelling

Given a class of objects, and a definition of “isomorphism”, we can choose one member of each isomorphism class and call it the canonical member of the class.

The process of finding the canonical member of the isomorphism class containing a given object is called “canonical labelling”.

computing sodo — 12

(36)

### Canonical labelling

Given a class of objects, and a definition of “isomorphism”, we can choose one member of each isomorphism class and call it the canonical member of the class.

The process of finding the canonical member of the isomorphism class containing a given object is called “canonical labelling”.

Two labelled objects which are isomorphic become identical when they are canonically labelled. Since identity of objects is usually far easier to check than isomorphism, canonical labelling is the preferred method of sorting a collection of objects into isomorphism classes.

computing sodo — 12

(37)

### Canonical labelling

Given a class of objects, and a definition of “isomorphism”, we can choose one member of each isomorphism class and call it the canonical member of the class.

The process of finding the canonical member of the isomorphism class containing a given object is called “canonical labelling”.

Two labelled objects which are isomorphic become identical when they are canonically labelled. Since identity of objects is usually far easier to check than isomorphism, canonical labelling is the preferred method of sorting a collection of objects into isomorphism classes.

A possible definition of the canonical member of an isomorphism class would be the member which maximises some linear representation (such as a list of edges).

In practice, most programs compute a canonical member which is easy for computers to find rather than easy for humans to define.

computing sodo — 12

(38)

### Software for graph isomorphism

This task was already described as a disease in 1970, and programs still appear regularly. The most successful programs still supported are:

### • nauty

(McKay, 1976–) canonical label and automorphism group

### • VF2

(Cordella, Foggia, Sansone and Vento, 1999–) comparison of two graphs

### • saucy

(Darga, Sakallah and Markov, 2004–) automorphism group

### • bliss

(Juntilla and Kaski, 2007–) canonical label and automorphism group

### • Traces

(Piperno, 2008–) canonical label and automorphism group

### • conauto

(L´opez-Presa, Anta and Chiroque, 2009–) automorphism group and comparison of two graphs

Many similar principles appear in these programs.

and

### bliss

began life as reimplementations of

### nauty

but have since diverged.

computing sodo — 13

(39)

### Partition refinement

A key concept used by

### nauty

is partition refinement. (“partition” = “colouring”) An equitable partition is one where every two vertices of the same colour are adjacent to the same number of vertices of each colour.

Two examples of equitable partitions:

computing sodo — 14

(40)

Refinement of a partition means to subdivide its cells.

Given a partition (colouring)

### π

, there is a unique equitable partition that is a refinement of

### π

and has the least number of colours.

computing sodo — 15

(41)

Refinement of a partition means to subdivide its cells.

Given a partition (colouring)

### π

, there is a unique equitable partition that is a refinement of

### π

and has the least number of colours.

Count green neighbours Initial

Count pink neighbours Count yellow neighbours

computing sodo — 15

(42)

### Search tree

All competitive isomorphism programs generate a tree based on partition refinement.

The nodes of the tree correspond to partitions (colourings).

The root of the tree corresponds to the initial colouring, refined.

If a node corresponds to a discrete partition (each vertex with a diﬀerent colour), it has no children and is a leaf.

Otherwise we choose a colour used more than once (the target cell), individualize one of those vertices by giving it a new unique colour, and refine to get a child.

computing sodo — 16

(43)

### Search tree

All competitive isomorphism programs generate a tree based on partition refinement.

The nodes of the tree correspond to partitions (colourings).

The root of the tree corresponds to the initial colouring, refined.

If a node corresponds to a discrete partition (each vertex with a diﬀerent colour), it has no children and is a leaf.

Otherwise we choose a colour used more than once (the target cell), individualize one of those vertices by giving it a new unique colour, and refine to get a child.

Each leaf lists the vertices in some order (since colours have a predefined order), so it corresponds to a labelling of the graph.

computing sodo — 16

(44)

### Search tree

All competitive isomorphism programs generate a tree based on partition refinement.

The nodes of the tree correspond to partitions (colourings).

The root of the tree corresponds to the initial colouring, refined.

If a node corresponds to a discrete partition (each vertex with a diﬀerent colour), it has no children and is a leaf.

Otherwise we choose a colour used more than once (the target cell), individualize one of those vertices by giving it a new unique colour, and refine to get a child.

Each leaf lists the vertices in some order (since colours have a predefined order), so it corresponds to a labelling of the graph.

If we have two leaves giving the same labelled graph, we have found an automorphism.

If we define an order on labelled graphs, such as lexicographic order, then the greatest labelled graph corresponding to a leaf is a canonical graph.

computing sodo — 16

(45)

### Search tree

All competitive isomorphism programs generate a tree based on partition refinement.

The nodes of the tree correspond to partitions (colourings).

The root of the tree corresponds to the initial colouring, refined.

If a node corresponds to a discrete partition (each vertex with a diﬀerent colour), it has no children and is a leaf.

Otherwise we choose a colour used more than once (the target cell), individualize one of those vertices by giving it a new unique colour, and refine to get a child.

Each leaf lists the vertices in some order (since colours have a predefined order), so it corresponds to a labelling of the graph.

If we have two leaves giving the same labelled graph, we have found an automorphism.

If we define an order on labelled graphs, such as lexicographic order, then the greatest labelled graph corresponding to a leaf is a canonical graph.

However the tree can be much too large to generate completely.

computing sodo — 16

(46)

4 5 [ 4 | | 5 | 2 7 | 6 | 3 ]1 8 [ 1 4 5 8 | 2 3 6 7 ]

3 4 1 2

8 7 6 5

[ 1 | 4 | 5 | 8 | 6 | 3 | 7 | 2 ] [ 1 | 5 | 4 | 8 | 3 | 6 | 7 | 2 ] [ 4 | 1 | 8 | 5 | 7 | 2 | 6 | 3 ] [ ... ] [ ... ] [ ... ]

[ ... ] [ ... ] [ ... ] [ ... ]

1

7

2

4 5 3

6

8 1

7 6

3

2 5

8 2 1

3 5 4

6 8

### (1) (3 6)(4 5) (1 4)(2 3)(5 8)(6 7)

4

[ 1 | | 8 | 3 6 | 7 | 2 ]

7

computing sodo — 17

(47)

### Node invariants

A node invariant is a value

(

### ν

) attached to each node in the tree that depends only on the combinatorial properties of

### ν

and its ancestors in the search tree (not on the labelling of the graph).

Moreover, the order of node invariants must be preserved by descendants:

Let

1

### , ν

2 be nodes at the same level in the search tree. If

### ν

1 is a descendant of

1, and

### ν

2 is a descendant of

2, then

(

1)

(

2) =⇒

(

1)

(

2)

### .

computing sodo — 18

(48)

### Node invariants

A node invariant is a value

(

### ν

) attached to each node in the tree that depends only on the combinatorial properties of

### ν

and its ancestors in the search tree (not on the labelling of the graph).

Moreover, the order of node invariants must be preserved by descendants:

Let

1

### , ν

2 be nodes at the same level in the search tree. If

### ν

1 is a descendant of

1, and

### ν

2 is a descendant of

2, then

(

1)

(

2) =⇒

(

1)

(

2)

For example,

(

) = �

(

)

(

��)

(

### ν

)�

is a node invariant with lexicographic ordering, where

��

### , . . . , ν

is the path from the root of the tree to

, and

### c

( ) is the number of colours.

computing sodo — 18

(49)

### Node invariants

A node invariant is a value

(

### ν

) attached to each node in the tree that depends only on the combinatorial properties of

### ν

and its ancestors in the search tree (not on the labelling of the graph).

Moreover, the order of node invariants must be preserved by descendants:

Let

1

### , ν

2 be nodes at the same level in the search tree. If

### ν

1 is a descendant of

1, and

### ν

2 is a descendant of

2, then

(

1)

(

2) =⇒

(

1)

(

2)

For example,

(

) = �

(

)

(

��)

(

### ν

)�

is a node invariant with lexicographic ordering, where

��

### , . . . , ν

is the path from the root of the tree to

, and

### c

( ) is the number of colours.

Let φ be the greatest node invariant of a leaf. Then the lexicographically greatest labelled graph corresponding to a leaf ν with φ(ν) =φ is a canonical graph.

computing sodo — 18

(50)

### Pruning operations

Node invariants, together with automorphisms, allow us to remove parts of the search tree without generating them.

1. If

1

### , ν

2 are nodes at the same level in the search tree and

(

1)

(

### ν

2), then no canonical labelling is descended from

1.

2. If

1

### , ν

2 are nodes at the same level in the search tree and

(

1) �=

(

### ν

2), then no labelled graph descended from

### ν

1 is the same as one descended from

2. 3. If

1

2 are nodes with

2 =

### ν

1g for an automorphism

, then

maps the subtree

descended from

### ν

1 onto the subtree descended from

### ν

2.

computing sodo — 19

(51)

### Pruning operations

Node invariants, together with automorphisms, allow us to remove parts of the search tree without generating them.

1. If

1

### , ν

2 are nodes at the same level in the search tree and

(

1)

(

### ν

2), then no canonical labelling is descended from

1.

2. If

1

### , ν

2 are nodes at the same level in the search tree and

(

1) �=

(

### ν

2), then no labelled graph descended from

### ν

1 is the same as one descended from

2. 3. If

1

2 are nodes with

2 =

### ν

1g for an automorphism

, then

maps the subtree

descended from

### ν

1 onto the subtree descended from

### ν

2.

Each of these observations enables us to prune parts of the search tree.

The hope is that the remaining parts will be small enough to compute.

computing sodo — 19

(52)

### Variations between programs

The competing programs vary from each other in ways that include:

1. Data structures

2. Strength of the refinement procedure 3. Order of traversal of the search tree 4. Means of discovering automorphisms 5. Processing of automorphisms

computing sodo — 20

(53)

### Stronger refinement — nauty “invariants”

Sometimes refinement to equitable partition is insuﬃcient to separate vertices with clearly diﬀerent combinatorial properties. Those properties can be used to make the refinement stronger.

computing sodo — 21

(54)

### Stronger refinement — nauty “invariants”

Sometimes refinement to equitable partition is insuﬃcient to separate vertices with clearly diﬀerent combinatorial properties. Those properties can be used to make the refinement stronger.

For example, we can count the number of 3-cycles and 4-cycles through each vertex:

computing sodo — 21

(55)

### Stronger refinement — nauty “invariants”

Sometimes refinement to equitable partition is insuﬃcient to separate vertices with clearly diﬀerent combinatorial properties. Those properties can be used to make the refinement stronger.

For example, we can count the number of 3-cycles and 4-cycles through each vertex:

computing sodo — 21

(56)

### Stronger refinement — nauty “invariants”

Sometimes refinement to equitable partition is insuﬃcient to separate vertices with clearly diﬀerent combinatorial properties. Those properties can be used to make the refinement stronger.

For example, we can count the number of 3-cycles and 4-cycles through each vertex:

computing sodo — 21

(57)

### Example of stronger refinement performance

Consider random quartic graphs with 1000 vertices.

### • nauty

(dense data structures) 5.6 seconds

### • nauty

(sparse data structures) 0.5 seconds

### • nauty

(count vertices at distance 2) 0.0014 seconds

computing sodo — 22

(58)

### Example of stronger refinement performance

Consider random quartic graphs with 1000 vertices.

### • nauty

(dense data structures) 5.6 seconds

### • nauty

(sparse data structures) 0.5 seconds

### • nauty

(count vertices at distance 2) 0.0014 seconds

The big problem with these methods is that the best refinement technique varies from one graph class to another.

The user has to know which one to choose, which few do.

computing sodo — 22

(59)

### Tree traversal order — a Traces innovation

computing sodo — 23

(60)

### Tree traversal order — a Traces innovation

computing sodo — 23

(61)

### Classical order: depth-first search

computing sodo — 23

(62)

### Tree traversal order — a Traces innovation

computing sodo — 23

(63)

### Tree traversal order — a Traces innovation

The problem with BFS is that automorphisms are discovered at leaves.

computing sodo — 23

(64)

### Tree traversal order — a Traces innovation

computing sodo — 24

(65)

### Tree traversal order — a Traces innovation

computing sodo — 24

(66)

### Traces: experimental paths

Experimental paths allow automorphism detection during breadth-first search.

computing sodo — 24

(67)

### Refinement traces – a Traces innovation

In all programs, for almost all graphs, most of the work involves partition refinement.

However, the result of partition refinement is often thrown away because the node invariant of the resulting node is unsuitable.

computing sodo — 25

(68)

### Refinement traces – a Traces innovation

In all programs, for almost all graphs, most of the work involves partition refinement.

However, the result of partition refinement is often thrown away because the node invariant of the resulting node is unsuitable.

To alleviate this problem,

### Traces

defines the node invariant to be a vector whose components are computed incrementally during the refinement. Then the refinement can often be aborted early. (This extends a technique introduced by

### bliss

.)

computing sodo — 25

(69)

### Refinement traces – a Traces innovation

In all programs, for almost all graphs, most of the work involves partition refinement.

However, the result of partition refinement is often thrown away because the node invariant of the resulting node is unsuitable.

To alleviate this problem,

### Traces

defines the node invariant to be a vector whose components are computed incrementally during the refinement. Then the refinement can often be aborted early. (This extends a technique introduced by

### bliss

.)

Count green neighbours Initial

Count pink neighbours Count yellow neighbours

A possible trace (not

### Traces

’ trace) is the number of colours at each step: (2,3,5,6).

computing sodo — 25

(70)

### Sparse automorphism detection — a saucy innovation

x

w v

y

equitable partition

(no other blue or green)

computing sodo — 26

(71)

### Sparse automorphism detection — a saucy innovation

x

w v

y

equitable partition

(no other blue or green)

x

w v

y

individualize

x

w v

y

individualize

### w

computing sodo — 26

(72)

### Sparse automorphism detection — a saucy innovation

x

w v

y

equitable partition

(no other blue or green)

x

w v

y

individualize

x

w v

y

individualize

### w

This discovers the automorphism (

)(

### x y

) without comparing leaves.

computing sodo — 26

(73)

### Automorphism group handling

Programs using depth-first search naturally produce automorphisms in the form of a base and strong generating set.

Other programs, like

### Traces

, produce less predictable generators.

In order to perform automorphism-based pruning of the search tree, we need to eﬃciently (usually) determine if two sequences of vertices are equivalent under the group generated by the automorphisms found so far.

computing sodo — 27

(74)

### Automorphism group handling

Programs using depth-first search naturally produce automorphisms in the form of a base and strong generating set.

Other programs, like

### Traces

, produce less predictable generators.

In order to perform automorphism-based pruning of the search tree, we need to eﬃciently (usually) determine if two sequences of vertices are equivalent under the group generated by the automorphisms found so far.

### Traces

uses a technique called the random Schreier method to perform this compu- tation probabiliistically.

### nauty

also uses this in circumstances where the basic group handling is insuﬃcient.

computing sodo — 27

(75)

101 102 103 105

104 103 102 101

Vertices

Time(sec)(sec)

Automorphism group

Bliss 7.2 Nauty 2.5 Conauto 2.0 Saucy 2.1 Traces 2.0

101 102 103

105 104 103 102 101

Vertices

Time(sec)(sec)

Canonical label

Bliss 7.2 Nauty 2.5 Traces 2.0

Figure 1: Random graphs with

### p

= 12

computing sodo — 28

(76)

102 103 104 105 104

103 102 101 100 101

102 >600s

Vertices

Time(sec)

Automorphism group

Bliss 7.2 Nauty 2.5 Conauto 2.0 Saucy 2.1 Traces 2.0

102 103 104 105 104

103 102 101 100 101

102 >600s

Vertices

Time(sec)

Canonical label

Bliss 7.2 Nauty 2.5 Traces 2.0

Figure 2: Random cubic graphs

computing sodo — 29

(77)

101 102 103 104 105 105

103 101 101

>600s

Vertices

Time(sec)

Automorphism group

Bliss 7.2 Nauty 2.5 Conauto 2.0 Saucy 2.1 Traces 2.0

101 102 103 104 105 105

103 101 101

>600s

Vertices

Time(sec)

Canonical label

Bliss 7.2 Nauty 2.5 Traces 2.0

Figure 3: Random trees

computing sodo — 30

(78)

101 102 103 104 105 106 105

103 101

101 >400s

Vertices

Time(sec)

Automorphism group

Bliss 7.2 Nauty 2.5 Conauto 2.0 Saucy 2.1 Traces 2.0

101 102 103 104 105 106 105

103 101 101

Vertices

Time(sec)

Canonical label

Bliss 7.2 Nauty 2.5 Traces 2.0

Figure 4: Hypercubes

computing sodo — 31

(79)

101 102 103 104 105

104 103 102 101 100

Vertices

Time(sec)

Automorphism group

Bliss 7.2 Nauty 2.5 Conauto 2.0 Saucy 2.1 Traces 2.0

101 102 103 104 105

104 103 102 101 100

Vertices

Time(sec)

Canonical label

Bliss 7.2 Nauty 2.5 Traces 2.0

Figure 5: Miscellaneous vertex-transitive graphs

computing sodo — 32

(80)

101 102 103 104 105

104 103 102 101 100

Vertices

Time(sec)

Automorphism group

Bliss 7.2 Nauty 2.5 Conauto 2.0 Saucy 2.1 Traces 2.0

101 102 103 104

105 104 103 102 101

Vertices

Time(sec)

Canonical label

Bliss 7.2 Nauty 2.5 Traces 2.0

Figure 6: 2-dimensional and 3-dimensional grids

computing sodo — 33

(81)

0 200 400 600 800 105

104 103 102 101

Vertices

Time(sec)

Automorphism group

Bliss 7.2 Nauty 2.5 Conauto 2.0 Saucy 2.1 Traces 2.0

0 200 400 600 800

105 104 103 102 101

Vertices

Time(sec)

Canonical label

Bliss 7.2 Nauty 2.5 Traces 2.0

Figure 7: Latin square graphs

computing sodo — 34

(82)

101 102 103 105

104 103 102 101 100 101

Vertices

Time(sec)

Automorphism group

Bliss 7.2 Nauty 2.5 Conauto 2.0 Saucy 2.1 Traces 2.0

101 102 103

105 104 103 102 101 100 101

Vertices

Time(sec)

Canonical label

Bliss 7.2 Nauty 2.5 Traces 2.0

Figure 8: Strongly regular graphs

computing sodo — 35

(83)

0 200 400 600 800 1,000 105

103 101 101

Vertices

Time(sec)

Automorphism group

Bliss 7.2 Nauty 2.5 Conauto 2.0 Traces 2.0

101 102 103

105 104 103 102 101 100 101 102

Vertices

Time(sec)

Canonical label

Bliss 7.2 Nauty 2.5 Traces 2.0

computing sodo — 36

(84)

104 105 101

100 101 102

>600s

Group Size

Time(sec)

Automorphism group

Bliss 7.2 Nauty 2.5 Conauto 2.0 Traces 2.0

104 105

101 100 101 102

>600s

Group Size

Time(sec)

Canonical label

Bliss 7.2 Nauty 2.5 Traces 2.0

Figure 10: Projective planes of order 16

computing sodo — 37

(85)

102.4 102.6 102.8 103 103.2 103

102 101 100

Vertices

Time(sec)

Automorphism group

Bliss 7.2 Nauty 2.5 Conauto 2.0 Traces 2.0

102.4 102.6 102.8 103 103.2 103

102 101 100 101

Vertices

Time(sec)

Canonical label

Bliss 7.2 Nauty 2.5 Traces 2.0

Figure 11: Cai-F¨urer-Immermann graphs

computing sodo — 38

(86)

102 103 104

103 102 101 100 101 102

>100s

Vertices

Time(sec)

Automorphism group

Bliss 7.2 Nauty 2.5 Conauto 2.0 Saucy 2.1 Traces 2.0

102 103

103 102 101 100 101 102

>100s

Vertices

Time(sec)

Canonical label

Bliss 7.2 Nauty 2.5 Traces 2.0

Figure 12: Miyazaki graphs

computing sodo — 39

References

Related documents

The second experi- ment compares our tree-based method for setting attribute weights to a simple weighting scheme based on gain ratio, a weighting scheme based on the ReliefF

The tree produces an enumeration of all equivalence structures which mentions all structures having arbitrarily large finite classes exactly once; it also enumerates some

elements) rather than random nodes. e., inserting an element with a key between the j-th and j + 1-th smallest key in the tree, into a random size-n priority tree. They obtained

As we will see below, the tree of tuples of a structure is the most natural labeled tree one can associate to a structure: it determines the structure up to isomorphism, it captures

At last, in Section 9, we introduce the notion of a partial 3-tree, which is a tree associated with a matroid M; some of whose vertices are labelled by members of a partition of

Terraces in phylogenetic tree space are sets of trees with identical optimality scores for a.. given data set, arising from

In the PDA model, new leaf nodes are uniformly added onto any edges of the existing tree, whereas the Yule tree selects a pendant edge randomly, and adds a new node onto this

All values were computed by drawing 1,000 fifty taxa trees from a uniform distribution and computing normalizing constants exactly using the algorithms described

Your aim now is to find a tree which realises your matrix: any two leaves x and y of the tree are connected by a sequence of edges and you require the weights of these edges to add

Mixtures of two sets of branch lengths on a tree of a given topology can give exactly the same expected site pattern frequencies as a tree of a different topology under the

The Swedish school authorities have drawn attention to this work and designated the school ‘the best school in Sweden working for equal value 2008’. Student empowerment, child’s

This paper proposes a genetic programming-based method to automatically generate fully au- tomated service compositions in a multi-objective context, based on a novel fragmented

Of particular interest is the reconstruction question: what number k of independent samples (partitions) are required to correctly reconstruct the underlying tree (with

The GPU kernel for computing SHAP values Given a unique decision tree path extracted from a decision tree in an ensemble predictor, with duplicates removed, we allocate one path

In this section, we recall two well known classes of metrics de ned on secondary structures, namely, base-pair and tree metrics, which are based on the bracket and tree

The algorithms we give for computing the size of the maximum agreement subtrees of unrooted trees can be modified for the rooted case, or to construct the

The tree produces an enumeration of all equivalence structures which mentions all structures having arbitrarily large finite classes exactly once; it also enumerates some

Sessional Com m ittee on the Environm ent 79.. A strong research and development effort, particularly into the integration of control methods, is essential to the

• Because all nodes in a tree (except the root node) are descendants of exactly one other node we can recursively think of each node being the root node of a smaller tree.. •

If treewidth of G is less than w produce a tree decomposition of G of width less than 4w in time O(f (w ) · mn), where m and n are the number of edges and nodes of G and f depends

An immediate next step could be the development of a QUBO for problems that are closely related to Tree Containment such as the problem of deciding if a given phylogenetic

Bayesian Event Tree for Eruption Forecasting (BET_EF) and Bayesian Event Tree for Volcanic Hazards (BET_VH) are recently developed PVHA software programs that are

existence. In making such an estimate, the Government Printer was requested to take as understood that each author body would have its report printed by the