boostorg / boostorg/graph

Interest along Weisfeiler-Leman Graph Isomorphism Test

Abierto
#451 2 comentarios 1 reacción 0 asignados Ver en GitHub
algorithm
Lenguaje dominante
C++
Estrellas
392
Forks
239
Merge medio
1 d 11 min
PR fusionados (30 d)
20

Descripción

Hi Graphies,

I received a feature request from a graph scientist: the Weisfeiler-Leman (WL) graph isomorphism test, a popular heuristic for detecting non-isomorphic graphs. From what I understand, WL quickly proves non-isomorphism in polynomial time, so one can skip exponential exact algorithm most of the time. So it should problably complement existing BGL algorothms like:
- `isomorphism()` Exact algorithm, worst-case exponential time
- `vf2_sub_graph_iso()` Subgraph matching, even slower

## Literature
- Founding article: [Weisfeiler & Leman, 1968](https://iti.zcu.cz/wl2018/pdf/wl_paper_translation.pdf)
- Power and Limits: [Kiefer 2020](https://publications.rwth-aachen.de/record/785831/files/785831.pdf)

What do you think ?

Guía de contribución

Abrir la guía de contribución

Evaluación

Este issue todavía no se ha evaluado.

Recibe los nuevos issues en tu correo

Un resumen breve de issues de GitHub para principiantes.