Isomorphism Checking in GROOVE

    Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

    17 Downloads (Pure)

    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.
    Original languageUndefined
    Title of host publicationGraph-Based Tools (GraBaTs)
    EditorsA. Zündorf, D. Varró
    PublisherEuropean Association of Software Science and Technology
    Pages-
    Number of pages11
    ISBN (Print)1863-2122
    Publication statusPublished - Sep 2007

    Publication series

    NameElectronic Communications of the EASST
    PublisherEuropean Association of Software Science and Technology
    NumberLNCS4549
    Volume1
    ISSN (Print)1863-2122

    Keywords

    • EWI-11048
    • IR-64346
    • METIS-241906

    Cite this