Page ComplexityAnalysis

Complexity analysis of algorithm sgip

Algorithm sgip

The major of our work focus on the generation of a family of distinguishing sets (some call resolving sets) {S_j}, each of which can give a deterministic order of all the vertices of Non-parity Set (a set of vertices without equivalent set ) by their distance coordinate in S_j. The vertices in G were initially partitioned by degree.

Complexity

Suppose S is a distinguishing set for G with cardinality s

$The running time of distance matrix should be O(n2) in Breadth-First-Search.

$the coordinates of V can be found within O(sn) time.

$Sorting the vertices by their coordinates, it takes O(sn^2) by Quick-Sort

$ The comparison takes n^2 time.

Summarizing, running time of canonization is bounded by n^2+(sn+sn^2+n^2 )(█(n@s))s! Cardinality of distinguishing set of strongly regular graphs (which is the worst case in our model) is bounded by O(s)=√n log⁡n So the complexity of sgip is o(n^(3+s) )=o(exp⁡(√n 〖log〗^2 n+3 log⁡n)) This is much better than o(exp⁡(2√n 〖log〗^2 n)) [L.BABAI,1980].

Comments