Colour refinement is at the heart of all the most efficient graph isomorphism software packages. In this paper we present a method for extending the applicability of refinement algorithms to directed graphs with weighted edges. We use Traces as a reference software, but the proposed solution is easily transferrable to any other refinement-based graph isomorphism tool in the literature. We substantiate the claim that the performances of the original algorithm remain substantially unchanged by showing experiments for some classes of benchmark graphs.
Isomorphism test for digraphs with weighted edges / Piperno, Adolfo. - ELETTRONICO. - (2018). (Intervento presentato al convegno 17th International Symposium on Experimental Algorithms tenutosi a L'Aquila) [10.4230/LIPIcs.SEA.2018].
Isomorphism test for digraphs with weighted edges
Adolfo Piperno
2018
Abstract
Colour refinement is at the heart of all the most efficient graph isomorphism software packages. In this paper we present a method for extending the applicability of refinement algorithms to directed graphs with weighted edges. We use Traces as a reference software, but the proposed solution is easily transferrable to any other refinement-based graph isomorphism tool in the literature. We substantiate the claim that the performances of the original algorithm remain substantially unchanged by showing experiments for some classes of benchmark graphs.| File | Dimensione | Formato | |
|---|---|---|---|
|
Piperno_Isomorphism_2018.pdf
accesso aperto
Tipologia:
Versione editoriale (versione pubblicata con il layout dell'editore)
Licenza:
Creative commons
Dimensione
1.43 MB
Formato
Adobe PDF
|
1.43 MB | Adobe PDF | |
|
Piperno_Isomorphism_2018-0.pdf
accesso aperto
Tipologia:
Versione editoriale (versione pubblicata con il layout dell'editore)
Licenza:
Creative commons
Dimensione
335.19 kB
Formato
Adobe PDF
|
335.19 kB | Adobe PDF |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
