RUS  ENG
Full version
JOURNALS // Proceedings of the Institute of Mathematics of the NAS of Belarus // Archive

Tr. Inst. Mat., 2022 Volume 30, Number 1-2, Pages 44–49 (Mi timb333)

Application of the clique minimal separator decomposition to finding the maximum weight $\{K_1,K_2,k,l\}$-packing in a graph

V. V. Lepin

Institute of Mathematics of the National Academy of Sciences of Belarus, Minsk

Abstract: The maximum weight $(\{ K_{1} ,K_{2} \} ,k,l)$-packing problem in graph is considered. This problem generalizes a number of well-known problems, for example: maximum induced matching, k-separated matching, connected matching, independent set, dissociating set, $k$-packing. Let $\Gamma $ be a class of graphs and $\Gamma^*$ the class of all atoms (with respect to the clique minimal separator decomposition) generated subgraphs from $\Gamma $. Proof that if the maximum weight $(\{ K_{1} ,K_{2} \} ,k,l)$-packing problem can be solve in the class of graphs $\Gamma^*$ in time $O(f_{atoms}(n)),$ then this problem can be solved in the class of graphs $\Gamma$ in time $O(n(n+m)\cdot f_{atoms}(n)).$

UDC: 517.9

Received: 18.11.2022



© Steklov Math. Inst. of RAS, 2025