Home         Authors   Papers   Year of conference   Themes   Organizations        To MES conference

A Method for Selecting an Isomorphic Subgraph of a Circuit Diagram Graph in Electronic Circuit CAD Systems
Authors
	Kurapov S.V.
	Davidovsky M.V.
Date of publication
	2021
DOI
	10.31114/2078-7707-2021-3-18-25
Abstract
	Studying the properties of objects based on the analysis of their structural characteristics constitute one of the most important and promising directions in the development of applied graph theory. In general, discrete graph models represent the structures of objects of a very different nature. Analysis of structural characteristics of the designed objects becomes notably important in the design of microcircuits, printed circuit boards, flexible printed circuit boards, integrated circuits, as well as LSI, VLSI and other flat con-structs design processes. Thus, a challenging task within the scope of modern CAD systems development activities is the problem of recognizing the structures of various designed objects. In order to increase the efficiency of CAD, in prac-tice, there is a need to use graph isomorphism testing – for example, to verify various representations of an electronic circuit when automating electronic circuits design. The article is devoted to applied mathematical methods for determining the isomorphism of subgraphs of circuit diagram graphs in electronic equipment CAD systems. In this work the authors present a method for solving the problem of extracting a subgraph G0 from graph G(V,E), which is iso-morphic to a given reference graph H(X,U). The method is based on the use of a complete invariant of a graph repre-senting its individual structure in numerical form. Preliminary determination of the complete invariant for the refer-ence graph allows reducing the problem to finding a set of subgraphs of the graph G with the number of vertices equal to the cardinality card(X) of the set of vertices of the graph H. The proposed solution consists in enumerating all sets of |X|-combinations from|V|. Such a problem statement allows applying computational methods with polynomial computational complexity to solve the original hard problem.
Keywords
	computer-aided design system, electrical schematic diagram graph, graph isomorphism, isomorphic subgraph extraction.
Library reference
	Kurapov S.V., Davidovsky M.V. A Method for Selecting an Isomorphic Subgraph of a Circuit Diagram Graph in Electronic Circuit CAD Systems // Problems of Perspective Micro- and Nanoelectronic Systems Development - 2021. Issue 3. P. 18-25. doi:10.31114/2078-7707-2021-3-18-25
URL of paper
	http://www.mes-conference.ru/data/year2021/pdf/D065.pdf