Isomorphism Checking in GROOVE
Rensink, Arend (2006) Isomorphism Checking in GROOVE. In: Third InternationalWorkshop on Graph Based Tools, GraBaTs 2006, 21-22 September 2006, Natal, Brazil.
|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.
|Item Type:||Conference or Workshop Item|
Electrical Engineering, Mathematics and Computer Science (EEMCS)
|Link to this item:||http://purl.utwente.nl/publications/64346|
|Export this item as:||BibTeX|
Daily downloads in the past month
Monthly downloads in the past 12 months
Repository Staff Only: item control page
Metis ID: 241906