Graph (regular) Isomorphism in n^(O(log2(n))) .

It is open for comments and suggestions.In summary, the conversation discusses an algorithm for graph regular isomorphism with a time complexity of n^(O(log2(n))). The algorithm uses an iterative approach and is open for comments and suggestions.
  • #1
secondprime
49
0
I am trying to construct an algorithm which is combinatorial in nature. I have shared a link-

https://www.academia.edu/11354697/Graph_regular_Isomorphism_in_n_O_log2_n_

which depicts the idea simply using an example. I claim (if it is correct) n^(O(log2(n))) time complexity.

happy to have comments!
 
Last edited by a moderator:
Physics news on Phys.org
  • #2
The algorithm proposed in the link is a graph regular isomorphism algorithm. It uses an iterative approach to find an isomorphism between two graphs with n vertices, by testing all possible combinations of n nodes. The time complexity of this algorithm is O(n^(O(log2(n)))). This means that the algorithm will take a polynomial amount of time to complete, depending on the size of the graph. As the number of vertices increases, the time complexity increases exponentially.
 

Related to Graph (regular) Isomorphism in n^(O(log2(n))) .

What is Graph Isomorphism?

Graph Isomorphism is a mathematical concept that refers to the relationship between two graphs. Two graphs are considered isomorphic if they have the same number of vertices, edges, and the same connectivity pattern.

What is a regular graph?

A regular graph is a graph where each vertex has the same number of edges. In other words, the degree of each vertex in a regular graph is equal.

What is the significance of n^(O(log2(n))) in Graph Isomorphism?

n^(O(log2(n))) is a complexity class that represents the running time of an algorithm. In the case of Graph Isomorphism, it indicates that the algorithm can run in polynomial time.

How does Graph Isomorphism relate to other mathematical concepts?

Graph Isomorphism is closely related to other concepts such as permutation groups, group theory, and combinatorial optimization. It has applications in various fields, including computer science, chemistry, and biology.

Can Graph Isomorphism be solved in polynomial time?

It is still an open question whether Graph Isomorphism can be solved in polynomial time. While there are algorithms that run in polynomial time for certain types of graphs, it is currently unknown if there exists a polynomial-time algorithm for all types of graphs.

Similar threads

Help to write a psudoecode (formal) of this procedure.
    • Programming and Computer Science
Replies
1
Views
913
MHB Proving the symmetry of self complementary graphs with n=4k+1
    • Set Theory, Logic, Probability, Statistics
Replies
1
Views
1K
Evaluate the complexity of this graph coloring algorithm
    • Engineering and Comp Sci Homework Help
Replies
1
Views
1K
Proving a (known isomorphic) graph is isomorphic
    • Calculus and Beyond Homework Help
Replies
6
Views
2K
Graph isomorphism problem-advance in complexity research
    • Topology and Analysis
Replies
1
Views
1K
Proof about isomorphism (Graph Theory)
    • Precalculus Mathematics Homework Help
Replies
3
Views
2K
A Three generations of Fermions from octonions Clifford alegbras
    • Beyond the Standard Models
2
Replies
61
Views
6K
Book plots position & force on the same graph, still gets right answer
    • Introductory Physics Homework Help
Replies
8
Views
269
A Uncovering the Combinatorial Origins of Yang-Mills Theory?
    • Beyond the Standard Models
Replies
2
Views
689
Proving uniqueness of almost irregular graphs with equal degrees for n=2k
    • Calculus and Beyond Homework Help
Replies
3
Views
2K

Hot Threads

Recent Insights

Back
Top