Applying Colored-Graph Isomorphism for Electrical Circuit Matching in Circuit Repository
In electrical engineering educational industrial applications it is often required for the students to build and analyze well-known circuits according to their syllabus. In this paper a colored graph isomorphism based model is discussed that is being developed to match two electrical circuits. The procedure involves two steps, first being, to store the circuit in the data base in form of a colored graph and then matching users input circuit with it using graph isomorphism. Since graph isomorphism is in NP, it has no known polynomial time solution. However, in this particular problem of circuits, the colors and weight used in the nodes vary and the graphs generated are sparsely connected. Thus the algorithm runs in a reasonable time.
Keywords: circuit matching, graph isomorphism, colored graph, circuits, circuit repository
Download Full-Text
ABOUT THE AUTHORS
Ananda Maiti
VIT University
Balakrushna Tripathy
Prof. B. K. Tripathy is a senior professor with the School of Computing Science and Engineering, VIT University, Vellore, India.
Ananda Maiti
VIT University
Balakrushna Tripathy
Prof. B. K. Tripathy is a senior professor with the School of Computing Science and Engineering, VIT University, Vellore, India.