Solving the problem of findingan independent $\{K_1,K_2\}$-packing of maximum weight in tree-cographs
Trudy Instituta matematiki, Tome 27 (2019) no. 1, pp. 53-59
Citer cet article
Voir la notice de l'article provenant de la source Math-Net.Ru
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_{H\in\mathcal{S},~H\cong K_1}V(H),$ and $F=\bigcup_{H\in\mathcal{S}}E(H).$ The problem of finding an independent $\{K_1,K_2\}$-packing of maximum weight is considered. We present a linear-time algorithm solving this problem for tree-cographs when the decomposition tree is a part of the input.
[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] 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
[3] Lepin V.V., “Reshenie zadachi o vzveshennoi nezavisimoi $\{K_1,K_2\}$-upakovke na grafakh so spetsialnymi blokami”, Trudy Instituta matematiki, 23:2 (2015), 62–71
[4] Tinhofer G., “Strong tree-cographs are Birkoff graphs”, Discrete Applied Mathematics, 22:3 (1989), 275–288