Geodesic
Application of the clique minimal separator decomposition to finding the maximum weight $\{K_1,K_2,k,l\}$-packing in a graph
Trudy Instituta matematiki, Tome 30 (2022) no. 1, pp. 44-49 
V. V. Lepin. Application of the clique minimal separator decomposition to finding the maximum weight $\{K_1,K_2,k,l\}$-packing in a graph. Trudy Instituta matematiki, Tome 30 (2022) no. 1, pp. 44-49. http://geodesic.mathdoc.fr/item/TIMB_2022_30_1_a5/
@article{TIMB_2022_30_1_a5,
     author = {V. V. Lepin},
     title = {Application of the clique minimal separator decomposition to finding the maximum weight $\{K_1,K_2,k,l\}$-packing in a graph},
     journal = {Trudy Instituta matematiki},
     pages = {44--49},
     year = {2022},
     volume = {30},
     number = {1},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/TIMB_2022_30_1_a5/}
}
TY  - JOUR
AU  - V. V. Lepin
TI  - Application of the clique minimal separator decomposition to finding the maximum weight $\{K_1,K_2,k,l\}$-packing in a graph
JO  - Trudy Instituta matematiki
PY  - 2022
SP  - 44
EP  - 49
VL  - 30
IS  - 1
UR  - http://geodesic.mathdoc.fr/item/TIMB_2022_30_1_a5/
LA  - ru
ID  - TIMB_2022_30_1_a5
ER  - 
%0 Journal Article
%A V. V. Lepin
%T Application of the clique minimal separator decomposition to finding the maximum weight $\{K_1,K_2,k,l\}$-packing in a graph
%J Trudy Instituta matematiki
%D 2022
%P 44-49
%V 30
%N 1
%U http://geodesic.mathdoc.fr/item/TIMB_2022_30_1_a5/
%G ru
%F TIMB_2022_30_1_a5

Voir la notice de l'article provenant de la source Math-Net.Ru

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)).$

[1] Yuster R., “Combinatorial and computational aspects of graph packing and graph decomposition”, Computer Science Review, 1:1 (2007), 12–26 | DOI | Zbl

[2] Joos F., Rautenbach D., “Equality of Distance Packing Numbers”, Discrete Mathematics, 338:12 (2015), 2374–2377 | DOI | MR | Zbl

[3] Brandstadt A., Mosca R., “On distance-3 matchings and induced matchings”, Discrete Applied Mathematics, 159:7 (2011), 509–520 | DOI | MR | Zbl

[4] Gavril F., “The intersection graphs of subtrees in trees are exactly the chordal graphs”, Journal of Combinatorial Theory, Series B, 16:1 (1974), 47–56 | DOI | MR | Zbl

[5] Leimer H. G., “Optimal decomposition by clique separators”, Discrete Mathematics, 113:1-3 (1993), 99–123 | DOI | MR | Zbl

[6] Tarjan R. E., “Decomposition by clique separators”, Discrete Math., 55 (1985), 221–232 | DOI | MR | Zbl

[7] Dirac G.A., “Onrigid circuit graphs”, Abh. Math. Sem. Univ. Hamburg, 25 (1961), 71–76 | DOI | MR | Zbl