= Adolfo Piperno
{c}
{tag=Computer science author}
\b[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.<Adolfo Piperno profile at Sapienza University of Rome>[Departmental profile and linked university research description]{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>.<Search Space Contraction in Canonical Labeling of Graphs by Adolfo Piperno>[Abstract and introduction, individualization/refinement and Traces]{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.<Practical graph isomorphism, II by Brendan D. McKay and Adolfo Piperno>[Abstract; framework and implementations]{ref}
Back to article page
