Leírás
Kivonat:
P.L.Hammer with collaborators in the 80's introduced a technique for
transformation an (unweighted) graph, such that the new graph's
stability number was one less, that is $\alpha(G)=\alpha(G')+1$. Using
this method they could prove that for some classes of graphs the
algorithm determining the exact stability number of the graph run in
polynomial time.
Nowadays several kernelization techniques are in use, mostly for the
vertex cover problem, that are descendants of this struction
transformation. Recently similar techniques emerged for the weighted
counterpart of these graph problems. The original struction paper
describes one method for weighted graphs, but it is not a general
method, nor a practical one.
The talk will describe new weighted versions of the struction
transformation and the ideas behind. It will also present the
numerical experiments comparing the new algorithm based on this
transformation with the previous algorithms. This work will be
presented on the ALENEX21 conference as a joined work with Alexander
Gellner, Sebastian Lamm, Christian Schulz and Darren Strash.