@inproceedings{1b2e8a701cfb449995a075054c36906a,

title = "Isomorphism Checking in GROOVE",

abstract = "In this paper we show how isomorphism checking can be used as an effective technique for symmetry reduction in graph-based state spaces, despite the inherent complexity of the isomorphism problem. In particular, we show how one can use element-based graph certificate mappings to help in recognising nonisomorphic graphs. These are mappings that assign to all elements (edges and nodes) of a given graph a number that is invariant under isomorphism, in the sense that any isomorphism between graphs is sure to preserve this number. The individual element certificates of a graph give rise to a certificate for the entire graph, which can be used as a hash key for the graph; hence, this yields a heuristic to decide whether a graph has an isomorphic representative in a previously computed set of graphs. We report some experiments that show the viability of this method.",

keywords = "EWI-11048, IR-64346, METIS-241906",

author = "Arend Rensink",

year = "2007",

month = sep,

language = "Undefined",

isbn = "1863-2122",

series = "Electronic Communications of the EASST",

publisher = "European Association of Software Science and Technology",

number = "LNCS4549",

pages = "--",

editor = "A. Z{\"u}ndorf and D. Varr{\'o}",

booktitle = "Graph-Based Tools (GraBaTs)",

}