Graph isomorphism—Characterization and efficient algorithms
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 o...
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Elsevier
2024-12-01
|
| Series: | High-Confidence Computing |
| Subjects: | |
| Online Access: | http://www.sciencedirect.com/science/article/pii/S2667295224000278 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Summary: | 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(n3). |
|---|---|
| ISSN: | 2667-2952 |