2016/05/30 by Thomas E. Portegys, Portegys, Thomas E.
Biochemistry, Genetics and Molecular Biology · Computer Science · #DNA and Biological Computing #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Graph Theory and Algorithms #Software Testing and Debugging Techniques
paper · pdf · doi:10.48550/arxiv.1606.00001
openalex publication_date 2016/05/30 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
A method for improving the efficiency of graph isomorphism testing is presented. The method uses the structure of the graph colored by vertex hash codes as a means of partitioning vertices into equivalence classes, which in turn reduces the combinatorial burden of isomorphism testing. Unrolling the graph into a tree at each vertex allows structurally different regular graphs to be discriminated, a capability that the color refinement algorithm cannot do.