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

doi:10.1109/DSD.2010.29

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 proceeding › Conference contribution › Academic › peer-review

6 Citations (Scopus)

252 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 language	Undefined
Title of host publication	Proceedings of the 13th Euromicro Conference on Digital System Design: Architectures, Methods and Tools, DSD 2010
Place of Publication	USA
Publisher	IEEE
Pages	699-705
Number of pages	7
ISBN (Print)	978-0-7695-4171-6
DOIs	https://doi.org/10.1109/DSD.2010.29
Publication status	Published - 3 Sept 2010
Event	13th EUROMICRO Conference on Digital System Design, DSD 2010: Architectures, Methods and Tools - Lille, France Duration: 1 Sept 2010 → 3 Sept 2010 Conference number: 13

Publication series

Name
Publisher	IEEE Computer Society

Conference

Conference	13th EUROMICRO Conference on Digital System Design, DSD 2010
Abbreviated title	DSD
Country/Territory	France
City	Lille
Period	1/09/10 → 3/09/10

Keywords

METIS-271013
EWI-18373
IR-73123

Access to Document

10.1109/DSD.2010.29

Cite this

@inproceedings{9b5d869f215847f9b76b80f2e1a90cca,

title = "An Approximate Maximum Common Subgraph Algorithm for Large Digital Circuits",

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.",

keywords = "METIS-271013, EWI-18373, IR-73123",

author = "J.H. Rutgers and P.T. Wolkotte and P.K.F. Holzenspies and Jan Kuper and Smit, {Gerardus Johannes Maria}",

note = "10.1109/DSD.2010.29 ; 13th EUROMICRO Conference on Digital System Design, DSD 2010 ; Conference date: 01-09-2010 Through 03-09-2010",

year = "2010",

month = sep,

day = "3",

doi = "10.1109/DSD.2010.29",

language = "Undefined",

isbn = "978-0-7695-4171-6",

publisher = "IEEE",

pages = "699--705",

booktitle = "Proceedings of the 13th Euromicro Conference on Digital System Design: Architectures, Methods and Tools, DSD 2010",

address = "United States",

}

Rutgers, JH, Wolkotte, PT, Holzenspies, PKF, Kuper, J & Smit, GJM 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. IEEE, USA, pp. 699-705, 13th EUROMICRO Conference on Digital System Design, DSD 2010, Lille, France, 1/09/10. https://doi.org/10.1109/DSD.2010.29

An Approximate Maximum Common Subgraph Algorithm for Large Digital Circuits. / Rutgers, J.H.; Wolkotte, P.T.; Holzenspies, P.K.F. et al.
Proceedings of the 13th Euromicro Conference on Digital System Design: Architectures, Methods and Tools, DSD 2010. USA: IEEE, 2010. p. 699-705.

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

TY - GEN

T1 - An Approximate Maximum Common Subgraph Algorithm for Large Digital Circuits

AU - Rutgers, J.H.

AU - Wolkotte, P.T.

AU - Holzenspies, P.K.F.

AU - Kuper, Jan

AU - Smit, Gerardus Johannes Maria

N1 - Conference code: 13

PY - 2010/9/3

Y1 - 2010/9/3

N2 - 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.

AB - 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.

KW - METIS-271013

KW - EWI-18373

KW - IR-73123

U2 - 10.1109/DSD.2010.29

DO - 10.1109/DSD.2010.29

M3 - Conference contribution

SN - 978-0-7695-4171-6

SP - 699

EP - 705

BT - Proceedings of the 13th Euromicro Conference on Digital System Design: Architectures, Methods and Tools, DSD 2010

PB - IEEE

CY - USA

T2 - 13th EUROMICRO Conference on Digital System Design, DSD 2010

Y2 - 1 September 2010 through 3 September 2010

ER -