English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

The Graph Isomorphism (GI) problem is a theoretically interesting problembecause it has not been proven to be in P nor to be NP-complete. Babai made abreakthrough in 2015 when announcing a quasipolynomial time algorithm for GIproblem. Babai's work gives the most theoretically efficient algorithm for GI,as well as a strong evidence favoring the idea that class GI $\ne$ NP and thusP $\ne$ NP. Based on Babai's algorithm, we prove that GI can further be solvedby a parallel algorithm that runs in polynomial time using a quasipolynomialnumber of processors. We achieve that result by identifying the bottlenecks inBabai's algorithms and parallelizing them. In particular, we prove that colorrefinement can be computed in parallel logarithmic time using a polynomialnumber of processors, and the $k$-dimensional WL refinement can be computed inparallel polynomial time using a quasipolynomial number of processors. Our worksuggests that Graph Isomorphism and GI-complete problems can be computedefficiently in a parallel computer, and provides insights on speeding upparallel GI programs in practice.

A polynomial time parallel algorithm for graph isomorphism using a quasipolynomial number of processors