|
|
|
||
|
One of the most important open problems in Computer Science is the question
whether two given graphs are isomorphic. This course covers the milestones
in graph isomorphism testing from the 1970s until now. We study several
algorithms that solve isomorphism-testing for restricted graph classes like
the class of trees and forests or bounded degree graphs and we finish by
studying the theoretical foundations of Babai's famous quasi-polynomial
algorithm.
Poslední úprava: Pangrác Ondřej, RNDr., Ph.D. (16.05.2025)
|
|
||
|
Martin Grohe and Pascal Schweitzer. 2020. The graph isomorphism problem. Commun. ACM 63, 11 (November 2020), 128-134. https://doi.org/10.1145/3372123 Poslední úprava: Pangrác Ondřej, RNDr., Ph.D. (16.05.2025)
|
|
||
|
Most decision problems encountered in computer science are either solvable by a polynomial algorithm or they are hard to a degree that there is no hope that a practically useful algorithm is ever found. A curious exception to this is the question whether two given graphs are isomorphic. While there is no polynomial algorithm to decide the question, there is also no proof that it is NP-hard. Recently, Babai has found a decision algorithm, which runs in quasi-polynomial time using group theoretical reasoning.
This course covers the milestones in graph isomorphism testing from the 1970s until now. We study several algorithms that solve isomorphism-testing for restricted graph classes like the class of trees and forests or bounded degree graphs and we finish by studying the theoretical foundations of Babai's algorithm. Poslední úprava: Pangrác Ondřej, RNDr., Ph.D. (16.05.2025)
|