May 21, 2013: Paul Bonsma: Tight Lower and Upper Bounds for the Complexity of Canonical Color Refinement
May 21, 2013 | Tight Lower and Upper Bounds for the Complexity of Canonical Color Refinement |
Room: Zi 5126 | Paul Bonsma |
12:30-13:30 | *Color refinement* (also known as naive vertex classification or partition refinement) is a very simple, yet extremely useful algorithm routine for graph isomorphism testing. Initially, all vertices of the graph are assigned the same color. Iteratively, two vertices that currently have the same color receive different colors if for some color c, they have a different number of neighbors of color c. This process stops if no further refinement is possible, resulting in a *stable coloring* of the graph. |