Exhaustive generation of graphs up to isomorphism --- temporal graphs

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. Our goal is to give an improved and more general implementation, which is extendible with user-defined filters for various graph properties.

The task is to design and implement new filters. In the typical scenario, we have a graph with some property, say it has at least k components, and we insert a new node. The question is whether the extended graph has at least k components or not. How can we answer this query as soon as possible?

Similar questions have been already considered in relation to temporal graphs [1].

Előfeltételek

The ideal applicant is an expert in C++ or has irresistible desire to become one.

Hivatkozások

[1] Michail, Othon. "An introduction to temporal graphs: An algorithmic perspective." Internet Mathematics 12, no. 4 (2016): 239-280.