Graph isomorphism—Characterization and efficient algorithms  

作　　者：Jian Ren Tongtong Li 

机构地区：[1]Department of Electrical and Computer Engineering,Michigan State University,East Lansing 48824,USA

出　　处：《High-Confidence Computing》2024年第4期48-55,共8页高置信计算(英文)

基　　金：supported in part by the U.S.National Science Foundation(CCF1919154 and ECCS-1923409).

摘　　要：The Graph isomorphism problem involves determining whether two graphs are isomorphic and the computational complexity required for this determination.In general,the problem is not known to be solvable in polynomial time,nor to be NP-complete.In this paper,by analyzing the algebraic properties of the adjacency matrices of the undirected graph,we first established the connection between graph isomorphism and matrix row and column interchanging operations.Then,we prove that for undirected graphs,the complexity in determining whether two graphs are isomorphic is at most O(n^(3)).

关 键 词：Undirected graph CHARACTERIZATION ISOMORPHISM ALGORITHM Polynomial time complexity 

分 类 号：O15[理学—数学]