Computer Science – Data Structures and Algorithms
Scientific paper
2010-07-10
Computer Science
Data Structures and Algorithms
39 pages;1.Added subsection 4.6.3; 2.New notation rdg(x) instead of rdeg(x) and d(x) (pages 5,6);3.New input for Algorithm A3
Scientific paper
New polynomial exact and heuristic algorithms for determining the generators, orbits and order of an undirected graph automorphism group are presented. A basic tool of these algorithms is the adjacency refinement procedure. Each node of the search tree used in the exact algorithm is a partition. A non-singleton cell with maximum partitioning ability is selected in each partition. The process of selections and refinement continues until a discrete partition is obtained. All nonequivalent discreet partitions are stored. Both algorithms have polynomial time and space complexity for any undirected graph with number of edges which is less or equal to half number of edges of the complete graph with the same number of vertices. This class of graphs we call ClassH. If the graph is not in the ClassH then we take the complement graph and apply the graph automorphism algorithm to its connected components and the graph isomorphism algorithm between these components. The polynomial complexities are based on a conjecture that the maximum value of the selection level is a constant 6 for any graph from ClassH. If during its execution some of the intermediate variables obtain a wrong value then the algorithm continues from a new start point loosing some of the results determined so far. The worst-case time and space complexities of the exact algorithm are O(n^7) and O(n^4), respectively. The tests of the exact algorithm for most of the known "difficult" graphs show lower running times than the widely known algorithms. The heuristic algorithm is based on determining some number of discreet partitions derivative of each vertex in the selected cell of the initial partition and comparing them for an automorphism. Its worst-case time and space complexities are O(n^5) and O(n), respectively. The heuristic algorithm is almost exact and is many times faster than the exact one.
No associations
LandOfFree
Polynomial time and space exact and heuristic algorithms for determining the generators, orbits and order of the graph automorphism group does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Polynomial time and space exact and heuristic algorithms for determining the generators, orbits and order of the graph automorphism group, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Polynomial time and space exact and heuristic algorithms for determining the generators, orbits and order of the graph automorphism group will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-300432