Leírás
Many interesting real world problems can be modeled by a suitable
graph, where a maximum or k-clique search can be performed to answer
the underlying question. Some of such problems lead to the question if
there is a k-clique in a given k-partite graph. Turan type extremal
questions arise naturally in this context, as for example: what is the
maximum number of edges of a k-clique free k-partite graph.
The talk will go along two parallel themes. First theme is about
practical algorithmic method for solving the k-clique problem in
k-partite graphs, such as preconditioning and other graph
transformations. We will show how having more instead of one
k-coloring of nodes can speed up the search. Second theme is about
extremal problems arising in connection with these preconditioning
methods and some possible consequences that can provide useful
information for graph transformations and solvability of the problem.
ZOOOOMMM!
Invite Link https://us06web.zoom.us/j/82873195695?pwd=lPy6CDPLhoUNvwyrBjvwmm4EkHuk9d.1
828 7319 5695
Passcode 809405