boostorg / boostorg/graph

Interest along Weisfeiler-Leman Graph Isomorphism Test

Offen
#451 2 Kommentare 1 Reaktion 0 zugewiesene Personen Auf GitHub ansehen
algorithm
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

Beitragsleitfaden öffnen

Bewertung

Dieses Issue wurde noch nicht bewertet.

Neue Issues direkt in Ihr Postfach

Eine kurze Übersicht über anfängerfreundliche GitHub-Issues.