A method of colored graph isomorphism problem

作者：Shang Huiliang; Zhang Qi; Tao Yudong; Zhang Chen; Kong Qingsheng^*

来源：Journal of Bionanoscience, 2013, 7(1): 26-33.

DOI：10.1166/jbns.2013.1100

• Circuit simulation methods
• Colored graph
• General graph
• Graph isomorphism
• Graph isomorphism problem
• Isomorphism problems

The colored graph isomorphism problem is a special version of the general graph isomorphism (GI) problem that involves confirming the existence of a color preserving isomorphism between a pair of colored graphs. It is widely studied, but most existing methods of colored graph isomorphism are bounded by color multiplicity. In this paper, we resolve this problem with an optimized circuit simulation method. This method is proved to be efficient in colored graph isomorphism problem and has no bound of color multiplicity. We further apply the proposed method in molecular isomorphism problem and obtain good performance.

• 出版日期2013
• 单位复旦大学