An Approximate Maximum Common Subgraph Algorithm for Large Digital Circuits

J.H. Rutgers, P.T. Wolkotte, P.K.F. Holzenspies, Jan Kuper, Gerardus Johannes Maria Smit

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

    5 Citations (Scopus)
    63 Downloads (Pure)

    Abstract

    This paper presents an approximate Maximum Common Subgraph (MCS) algorithm, specifically for directed, cyclic graphs representing digital circuits. Because of the application domain, the graphs have nice properties: they are very sparse; have many different labels; and most vertices have only one predecessor. The algorithm iterates over all vertices once and uses heuristics to find the MCS. It is linear in computational complexity with respect to the size of the graph. Experiments show that very large common subgraphs were found in graphs of up to 200,000 vertices within a few minutes, when a quarter or less of the graphs differ. The variation in run-time and quality of the result is low.
    Original languageUndefined
    Title of host publicationProceedings of the 13th Euromicro Conference on Digital System Design: Architectures, Methods and Tools, DSD 2010
    Place of PublicationUSA
    PublisherIEEE Computer Society
    Pages699-705
    Number of pages7
    ISBN (Print)978-0-7695-4171-6
    DOIs
    Publication statusPublished - 3 Sep 2010
    Event13th EUROMICRO Conference on Digital System Design, DSD 2010: Architectures, Methods and Tools - Lille, France
    Duration: 1 Sep 20103 Sep 2010
    Conference number: 13

    Publication series

    Name
    PublisherIEEE Computer Society

    Conference

    Conference13th EUROMICRO Conference on Digital System Design, DSD 2010
    Abbreviated titleDSD
    CountryFrance
    CityLille
    Period1/09/103/09/10

    Keywords

    • METIS-271013
    • EWI-18373
    • IR-73123

    Cite this

    Rutgers, J. H., Wolkotte, P. T., Holzenspies, P. K. F., Kuper, J., & Smit, G. J. M. (2010). An Approximate Maximum Common Subgraph Algorithm for Large Digital Circuits. In Proceedings of the 13th Euromicro Conference on Digital System Design: Architectures, Methods and Tools, DSD 2010 (pp. 699-705). USA: IEEE Computer Society. https://doi.org/10.1109/DSD.2010.29