An Approximate Maximum Common Subgraph Algorithm for Large Digital Circuits

Rutgers, Jochem H. and Wolkotte, Pascal T. and Hölzenspies, Philip K.F. and Kuper, Jan and Smit, Gerard J.M. (2010) An Approximate Maximum Common Subgraph Algorithm for Large Digital Circuits. In: 13th Euromicro Conference on Digital System Design, DSD 2010, 1-3 September 2010, Lille, France.

Preview

PDF
417Kb

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.
Item Type:	Conference or Workshop Item
Copyright:	© 2010 IEEE
Faculty:	Electrical Engineering, Mathematics and Computer Science (EEMCS)
Research Group:	Computer Architecture for Embedded Systems (CAES)
Link to this item:	http://purl.utwente.nl/publications/73123
Official URL:	http://dx.doi.org/10.1109/DSD.2010.29
Export this item as:	BibTeX EndNote HTML Citation Reference Manager

Repository Staff Only: item control page

Metis ID: 271013