Name
Abstract | ||
|---|---|---|
The k-dimensional Weisfeiler-Leman procedure (k-WL), which colors k-tuples of vertices in rounds based on the neighborhood structure in the graph, has proven to be immensely fruitful in the algorithmic study of Graph Isomorphism. More generally, it is of fundamental importance in understanding and exploiting symmetries in graphs in various settings. Two graphs are k-WL-equivalent if the k-dimensional Weisfeiler-Leman procedure produces the same final coloring on both graphs. 1-WL-equivalence is known as fractional isomorphism of graphs, and the k-WL-equivalence relation becomes finer as k increases. |
Year | DOI | Venue |
|---|---|---|
2022 | 10.1016/j.ic.2021.104803 | Information and Computation |
Keywords | DocType | Volume |
Weisfeiler-Leman algorithm,Graph packing problem,Fractional graph parameters,Linear-programming relaxation | Journal | 288 |
ISSN | Citations | PageRank |
0890-5401 | 0 | 0.34 |
References | Authors | |
0 | 4 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Vikraman Arvind | 1 | 0 | 0.34 |
| Frank Fuhlbrück | 2 | 0 | 2.03 |
| Johannes Köbler | 3 | 0 | 0.34 |
| Oleg Verbitsky | 4 | 191 | 27.50 |