MA015 Graph Algorithms

Lecture VI - Graph Isomorphism

Dates

28.11. rooted tree isomorphism (AHU algorithm), tree isomorphism
05.12. colour refinement

Reading

For rooted tree isomorphism, read the original Aho-Hopcrodt-Ullman book [PDF]
(the algorithm propper starts at page 84, you can skip the previous pages if not interested)

For tree isomorphism:
Douglas M. Campbell and David Radford (1991): "Tree Isomorphism Algorithms: Speed vs. Clarity". Mathematics Magazine, Vol. 64, No. 4 (Oct., 1991), pp. 252-261 [JSTOR]

For colour refinement:
Progress of various Colour Refinement algorithms when executed on the graph $P_6$ [PDF]
slides ;)

Additional material

The Nauty Traces tool.

Slides

Následující