Interest along Weisfeiler-Leman Graph Isomorphism Test
- Ngôn ngữ chính
- C++
- Star
- 392
- Fork
- 239
- Merge trung bình
- 1 ngày 11 phút
- Pull request đã merge (30 ngày)
- 20
Mô tả
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 ?
Hướng dẫn đóng góp
Đánh giá
Issue này chưa được đánh giá.