|
| | | | |
| | | |
| Stat |
Members: 3645
Articles: 2'504'928
Articles rated: 2609
26 April 2024 |
|
| | | | |
|
Article overview
| |
|
|
A polynomial time parallel algorithm for graph isomorphism using a quasipolynomial number of processors | | Duc Hung Pham
; Krishna V. Palem
; M. V. Panduranga Rao
; | | Date: |
11 Feb 2020 | | Abstract: | The Graph Isomorphism (GI) problem is a theoretically interesting problem
because it has not been proven to be in P nor to be NP-complete. Babai made a
breakthrough in 2015 when announcing a quasipolynomial time algorithm for GI
problem. Babai’s work gives the most theoretically efficient algorithm for GI,
as well as a strong evidence favoring the idea that class GI $
e$ NP and thus
P $
e$ NP. Based on Babai’s algorithm, we prove that GI can further be solved
by a parallel algorithm that runs in polynomial time using a quasipolynomial
number of processors. We achieve that result by identifying the bottlenecks in
Babai’s algorithms and parallelizing them. In particular, we prove that color
refinement can be computed in parallel logarithmic time using a polynomial
number of processors, and the $k$-dimensional WL refinement can be computed in
parallel polynomial time using a quasipolynomial number of processors. Our work
suggests that Graph Isomorphism and GI-complete problems can be computed
efficiently in a parallel computer, and provides insights on speeding up
parallel GI programs in practice. | | Source: | arXiv, 2002.4638 | | Services: | Forum | Review | PDF | Favorites | |
|
|
No review found.
Did you like this article?
Note: answers to reviews or questions about the article must be posted in the forum section.
Authors are not allowed to review their own article. They can use the forum section.
browser Mozilla/5.0 AppleWebKit/537.36 (KHTML, like Gecko; compatible; ClaudeBot/1.0; +claudebot@anthropic.com)
|
| |
|
|
|
|
News, job offers and information for researchers and scientists:
| |
REGISTER