The Weisfeiler-Leman dimension of conjunctive queries
A graph parameter is a function 𝑓 on graphs with the property that, for any pair of isomorphic graphs 𝐺1 and 𝐺2, 𝑓 (𝐺1) = 𝑓 (𝐺2). The Weisfeiler–Leman (WL) dimension of 𝑓 is the minimum 𝑘 such that, if 𝐺1 and 𝐺2 are indistinguishable by the 𝑘-dimensional WL-algorithm then 𝑓 (𝐺1) = 𝑓 (𝐺2). The WL-dim...
| Main Authors: | , , |
|---|---|
| Format: | Conference item |
| Language: | English |
| Published: |
Association for Computing Machinery
2024
|