@book{34193ab64b8c46839991c6eace3955e8,
title = "Using Canonical Forms for Isomorphism Reduction in Graph-based Model Checking",
abstract = "Graph isomorphism checking can be used in graph-based model checking to achieve symmetry reduction. Instead of one-to-one comparing the graph representations of states, canonical forms of state graphs can be computed. These canonical forms can be used to store and compare states. However, computing a canonical form for a graph is computationally expensive. Whether computing a canonical representation for states and reducing the state space is more efficient than using canonical hashcodes for states and comparing states one-to-one is not a priori clear. In this paper these approaches to isomorphism reduction are described and a preliminary comparison is presented for checking isomorphism of pairs of graphs. An existing algorithm that does not compute a canonical form performs better that tools that do for graphs that are used in graph-based model checking. Computing canonical forms seems to scale better for larger graphs.",
keywords = "Graph Isomorphism, IR-72368, EWI-18116, Graph-based Model Checking, METIS-276046, Canonical Form",
author = "Gijs Kant",
year = "2010",
month = jul,
language = "Undefined",
series = "CTIT Technical Report Series",
publisher = "Centre for Telematics and Information Technology (CTIT)",
number = "TR-CTIT-10-28",
address = "Netherlands",
}