Interest along Weisfeiler-Leman Graph Isomorphism Test
- Vorherrschende Sprache
- C++
- Sterne
- 392
- Forks
- 239
- Ø Merge
- 1 T. 11 Min.
- Gemergte PRs (30 T.)
- 20
Beschreibung
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 ?
Beitragsleitfaden
Bewertung
Dieses Issue wurde noch nicht bewertet.