Geodesic
Solving the problem of finding an independent $\{K_1,K_2\}$-packing of maximum weight on graphs with special blocks
Trudy Instituta matematiki, Tome 23 (2015) no. 2, pp. 62-71 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

Let $\mathcal{H}$ be a fixed set of connected graphs. A $\mathcal{H}$-packing of a given graph $G$ is a pairwise vertex-disjoint set of subgraphs of $G,$ each isomorphic to a member of $\mathcal{H}$. An independent $\mathcal{H}$-packing of a given graph $G$ is an $\mathcal{H}$-packing of $G$ in which no two subgraphs of the packing are joined by an edge of $G$. Given a graph $G$ with a vertex weight function $\omega_V:~V(G)\to\mathbb{N}$ and an edge weight function and $\omega_E:~E(G)\to\mathbb{N}$. Weight of an independent $\{K_1,K_2\}$-packing $S$ in $G$ is $\sum_{v\in U}\omega_V(v)+\sum_{e\in F}\omega_E(e),$ where $U=\bigcup_{G_i\in\mathcal{S},~G_i\cong K_1}V(G_i),$ and $F=\bigcup_{G_i\in\mathcal{S}}E(G_i)$. The problem of finding an independent $\{K_1,K_2\}$-packing of maximum weight is considered. We present an algorithm to solve this problem for graphs in which each block is a clique, a cycle or a complete bipartite graph. This class of graphs include trees, block graphs, cacti and block-cactus graphs. The time complexity of the algorithm is $O(n^2m),$ where $n=|V(G)|$ and $m=|E(G)|$. 
@article{TIMB_2015_23_2_a7,
     author = {V. V. Lepin},
     title = {Solving the problem of finding an independent $\{K_1,K_2\}$-packing of maximum weight on graphs with special blocks},
     journal = {Trudy Instituta matematiki},
     pages = {62--71},
     year = {2015},
     volume = {23},
     number = {2},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/TIMB_2015_23_2_a7/}
}
TY  - JOUR
AU  - V. V. Lepin
TI  - Solving the problem of finding an independent $\{K_1,K_2\}$-packing of maximum weight on graphs with special blocks
JO  - Trudy Instituta matematiki
PY  - 2015
SP  - 62
EP  - 71
VL  - 23
IS  - 2
UR  - http://geodesic.mathdoc.fr/item/TIMB_2015_23_2_a7/
LA  - ru
ID  - TIMB_2015_23_2_a7
ER  - 
%0 Journal Article
%A V. V. Lepin
%T Solving the problem of finding an independent $\{K_1,K_2\}$-packing of maximum weight on graphs with special blocks
%J Trudy Instituta matematiki
%D 2015
%P 62-71
%V 23
%N 2
%U http://geodesic.mathdoc.fr/item/TIMB_2015_23_2_a7/
%G ru
%F TIMB_2015_23_2_a7
V. V. Lepin. Solving the problem of finding an independent $\{K_1,K_2\}$-packing of maximum weight on graphs with special blocks. Trudy Instituta matematiki, Tome 23 (2015) no. 2, pp. 62-71. http://geodesic.mathdoc.fr/item/TIMB_2015_23_2_a7/

[1] Lepin V.V., “Algoritmy dlya nakhozhdeniya nezavisimoi $\{K_1,K_2\}$-upakovki naibolshego vesa v grafe”, Trudy Instituta matematiki, 22:1 (2014), 78–97

[2] Cameron K., Hell P., “Independent packings in structured graphs”, Math. Program. Ser. B, 105 (2006), 201–213 | DOI | MR | Zbl

[3] Lozin V. V., “On maximum induced matchings in bipartite graphs”, Information Processing Letters, 81 (2002), 7–11 | DOI | MR | Zbl

[4] Stockmeyer L. J., Vazirani V. V., “NP-completeness of some generalizations of the maximum matching problem”, Information Processing Letters, 15 (1982), 14–19 | DOI | MR | Zbl

[5] Ko C. W., Shepherd F. B., “Bipartite domination and simultaneous matroid covers”, SIAM J. Discrete Mathematics, 16 (2003), 327–349 | MR

[6] Alekseev V. E., Boliac R., Korobitsyn D. V., Lozin V. V., “NP-hard graph problems and boundary classes of graphs”, Theor. Comp. Science, 389:1–2 (2007), 219–236 | DOI | MR | Zbl

[7] Boliac R., Cameron K., Lozin V. V., “On computing the dissociation number and the induced matching number of bipartite graphs”, Ars Comb., 72 (2004), 241–253 | MR | Zbl

[8] Kardos F., Katrenic J., Schiermeyer I., “On computing the minimum 3-path vertex cover and dissociation number of graphs”, Theoretical Computer Science, 412:50 (2011), 7009–7017 | DOI | MR | Zbl

[9] Lozin V. V., Rautenbach D., “Some results on graphs without long induced paths”, Inf. Process. Lett., 88:4 (2003), 167–171 | DOI | MR | Zbl

[10] Orlovich Y., Dolgui A., Finke G., Gordon V., Werner F., “The complexity of dissociation set problems in graphs”, Discrete Applied Mathematics, 159:13 (2011), 1352–1366 | DOI | MR | Zbl

[11] Yannakakis M., “Node-deletion problems on bipartite graphs”, SIAM J. Computing, 10 (1981), 310–327 | DOI | MR | Zbl

[12] Cameron K., “Brambles and independent packings in chordal graphs”, Discr. Math., 309:18 (2009), 5766–5769 | DOI | MR | Zbl

[13] Kobler D., Rotics U., “Finding maximum induced matchings in subclasses of claw-free and $P_5$-free graphs, and in graphs with matching and induced matching of equal maximum size”, Algorithmica, 37 (2003), 327–346 | DOI | MR | Zbl

[14] Lepin V.V., “Lineinyi algoritm dlya nakhozhdeniya maksimalnogo indutsirovannogo parosochetaniya naimenshego vesa v reberno-vzveshennom dereve”, Trudy Instituta matematiki, 15:1 (2007), 78–90 | MR

[15] Cameron K., Sritharan R., Tang Y., “Finding a maximum induced matching in weakly chordal graphs”, Discrete Mathematics, 266 (2003), 133–142 | DOI | MR | Zbl

[16] Faudree R. J., Gyárfás A., Schelp R. H., Tuza Zs., “Induced matchings in bipartite graphs”, Discrete Mathematics, 78 (1989), 83–87 | DOI | MR | Zbl

[17] Fricke G., Laskar R. C., “Strong matchings on trees”, Congressus Numerantium, 89 (1992), 239–243 | MR | Zbl

[18] Moser H., Sikdar S., “The parameterized complexity of induced matching problem”, Discr. Appl. Math., 157 (2009), 715–727 | DOI | MR | Zbl

[19] Lozin V. V., “On maximum induced matchings in bipartite graphs”, Information Processing Letters, 81:1 (2002), 7–11 | DOI | MR | Zbl

[20] Lepin V.V., “Reshenie zadachi o vzveshennoi nezavisimoi $\{K_1,K_2\}$-upakovke na grafakh s ogranichennoi drevesnoi shirinoi”, Trudy Instituta matematiki, 23:1 (2015), 98–114 | MR

[21] Tarjan R. E., “Depth-first search and linear graph algorithms”, SIAM J. Computing, 1 (1972), 146–160 | DOI | MR | Zbl