Adolfo Piperno

Adolfo Piperno is a computer scientist at Sapienza University of Rome whose work includes algorithms for graph isomorphism and graph canonical labeling. His institutional profile identifies him in the Department of Computer Science.^[ref]

Piperno introduced the approach implemented in Traces graph isomorphism software, studying how to reduce the search needed for canonical labeling. His paper examines refinement of vertex classes, the choice of vertices to individualize, search order and the use of discovered graph automorphisms.^[ref]

An original small example illustrates individualization-refinement graph search. For the four-vertex path $1-2-3-4$, grouping vertices by their numbers of neighbors first gives classes $\{1,4\}$ and $\{2,3\}$. Give vertex1 a unique marker. Neighbor counts relative to that singleton then distinguish vertex2 from vertex3, and further refinement separates the remaining vertices. Choosing vertex4 instead produces the reflected ordering. A canonical-labeling procedure must account for such equivalent choices rather than depend on the input vertex names.

This example explains the basic mechanism, not every heuristic in Traces. Piperno and Brendan McKay later described both nauty and Traces within a common framework and compared their behavior on graph families.^[ref]