Isomorphism Checking in GROOVE

Share/Save/Bookmark

Rensink, Arend (2006) Isomorphism Checking in GROOVE. In: Third InternationalWorkshop on Graph Based Tools, GraBaTs 2006, 21-22 September 2006, Natal, Brazil.

[img]
Preview
PDF
123Kb
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
Faculty:
Electrical Engineering, Mathematics and Computer Science (EEMCS)
Research Group:
Link to this item:http://purl.utwente.nl/publications/64346
Official URL:http://eceasst.cs.tu-berlin.de/index.php/eceasst/article/view/77/84
Export this item as:BibTeX
EndNote
HTML Citation
Reference Manager

 

Repository Staff Only: item control page

Metis ID: 241906