Leírás
In this lecture, we give an overview of the ongoing collaboration with the
Slovenian applied mathematicians and computer scientists. In the first half
of the lecture, we introduce the degree and neighbor degree sequence
problem arising in H-NMR spectroscopy. While the general degree and
neighbor degree sequence problem is known to be NP-complete, the special
case needed for chemical structure prediction from H-NMR data is polynomial
solvable.
In the second half of the lecture we will present graph algorithm based
methods for solving different kind of combinatorial optimization problems.
We will demonstrate different problems and their graph models. The special
class of k-partite graphs, where the question is to deside if there is a
k-clique present is introduced. Due to the properies of these graphs we
will show effective preconditioning methods -- old and novel ones --
aiding the solution of such questions. Finally, we will demonstrate the
effectiveness of this method by comparative experiments.