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í