Exhaustive generation of graphs up to isomorphism
| Témavezető: | Madarasi Péter |
| ELTE TTK, Operációkutatási Tsz. | |
| email: | madarasip@staff.elte.hu |
Projekt leírás
Efficient algorithms for generating all small graphs up to isomorphism are based on canonical labeling processes that compute a canonical ("distinguished") node labeling of a graph. Combining the naive backtracking algorithm for generating all labeled graphs with the aforementioned canonical labeling process in a non-trivial way, one can enumerate all graphs up to isomorphism.
The goal of this project is to give an improved and more general implementation, which is extendible with user-defined filters for various graph properties.
Előfeltételek
The ideal applicant dreams in C++, uses python, understands C, and has no nightmares about elementary group theory.
Hivatkozások
[1] McKay, B.D., 1998. Isomorph-free exhaustive generation. Journal of Algorithms, 26(2), pp.306-324.