Interest along Weisfeiler-Leman Graph Isomorphism Test
- 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
Evaluación
Este issue todavía no se ha evaluado.