11 citations · 21 across the 7 of their papers we have counts for
Showing 2019Show all
3 papers · 1 filter
cs.DM2019★ 11 cited
The Power of the Weisfeiler-Leman Algorithm to Decompose Graphs
Sandra Kiefer, Daniel Neuen
The Weisfeiler-Leman procedure is a widely-used technique for graph isomorphism testing that works by iteratively computing an isomorphism-invariant coloring of vertex tuples. Mean…
cs.FL2019
String-to-String Interpretations with Polynomial-Size Output
Mikołaj Bojańczyk, Sandra Kiefer, Nathan Lhote
String-to-string MSO interpretations are like Courcelle's MSO transductions, except that a single output position can be represented using a tuple of input positions instead of jus…
cs.DM2019
A Linear Upper Bound on the Weisfeiler-Leman Dimension of Graphs of Bounded Genus
Martin Grohe, Sandra Kiefer
The Weisfeiler-Leman (WL) dimension of a graph is a measure for the inherent descriptive complexity of the graph. While originally derived from a combinatorial graph isomorphism te…