Loading...
Please wait, while we are loading the content...
Similar Documents
Electronic Communications of the EASST Volume 1 ( 2006 ) Proceedings of the Third International Workshop on Graph Based Tools ( GraBaTs 2006 ) Isomorphism Checking in GROOVE
| Content Provider | Semantic Scholar |
|---|---|
| Author | Rensink, Arend |
| Copyright Year | 2007 |
| Abstract | In this paper we show how isomorphism checking can be used as a n effective technique for symmetry reduction in graph-based tate spaces, despite the inherent complexity of the isomorphism problem. In part icular, we show how one can use lement-based graph certificate mappings to help in recognising nonisomorphic graphs. These are mappings that assign to all ele ments (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 e ntire graph, which can be used as a hash key for the graph; hence, this yields a heuris tic to decide whether a graph has an isomorphic representative in a previously comp uted set of graphs. We report some experiments that show the viability of this meth od. |
| File Format | PDF HTM / HTML |
| Alternate Webpage(s) | http://doc.utwente.nl/64346/1/grabats-revised.pdf |
| Alternate Webpage(s) | http://eprints.eemcs.utwente.nl/11048/01/grabats-revised.pdf |
| Language | English |
| Access Restriction | Open |
| Content Type | Text |
| Resource Type | Article |
