boostorg / boostorg/graph

Interest along Weisfeiler-Leman Graph Isomorphism Test

Đang mở
#451 2 bình luận 1 reaction 0 người được giao Xem trên GitHub
algorithm
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

Mở hướng dẫn đóng góp

Đánh giá

Issue này chưa được đánh giá.

Nhận issue mới trong hộp thư của bạn

Bản tóm tắt ngắn những issue GitHub phù hợp với người mới.