Graph isomorphism testing boosted by path coloring
| Autor: | Portegys, Thomas E. |
|---|---|
| Rok vydání: | 2016 |
| Předmět: | |
| Druh dokumentu: | Working Paper |
| Popis: | 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. Comment: arXiv admin note: text overlap with arXiv:1512.07263 |
| Databáze: | arXiv |
| Externí odkaz: |
|