.png){kind=icon}
.png){kind=icon}
Return
Graph isomorphism-Characterization and efficient algorithms
.png){kind=icon}
OA
AI
DOI：10.1016/j.hcc.2024.100224.png)
.png){kind=icon}
.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
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 ). (c) 2024 The Author(s). Published by Elsevier B.V. on behalf of Shandong University. This is an open access article under the CC BY-NC-ND license (http://creativecommons.org/licenses/by-nc-nd/4.0/).
Keywords:
Undirected graph
Characterization
Isomorphism
Algorithm
Polynomial time complexity
AI Summary
Key information extracted from the uploaded paper, including a brief overview, abstract, background, key highlights, visual analysis, and future outlook.
Journal
H
IF:
3
Papers:
239
Citations:
407