RUS  ENG JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB
 General information Latest issue Archive Search papers Search references RSS Latest issue Current issues Archive issues What is RSS

 Tr. Inst. Mat.: Year: Volume: Issue: Page: Find

 Tr. Inst. Mat., 2014, Volume 22, Number 1, Pages 78–97 (Mi timb210)

Algorithms for finding an independent $\{K_1,K_2\}$-packing of maximum weight in a graph

V. V. Lepin

Institute of Mathematics of the National Academy of Sciences of Belarus

Abstract: 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 algorithms to solve this problem for trees in time $O(n)$, for unicyclic graphs in time $O(n^2)$, and cographs and thin spider graphs in time $O(n+m)$, for co-gem-free graphs in time $O(m(m+n))$, where $n$ and $m$ are the number of vertices and edges in the graph. Moreover, we give a robust $O(m(m+n))$ time algorithm solving this problem for the graph class $\mathcal{T}\cup\mathcal{U}\cup\mathcal{G}_1\cup\mathcal{G}_2\cup\mathcal{G}_3$, where $\mathcal{T}$ — trees, $\mathcal{U}$ — unicycle, $\mathcal{G}_1$ — (bull,fork)-free, $\mathcal{G}_2$ — (co-P,fork)-free, $\mathcal{G}_3$ — ($P_5,$fork)-free graphs.

Full text: PDF file (410 kB)
References: PDF file   HTML file
UDC: 519.1

Citation: V. V. Lepin, “Algorithms for finding an independent $\{K_1,K_2\}$-packing of maximum weight in a graph”, Tr. Inst. Mat., 22:1 (2014), 78–97

Citation in format AMSBIB
\Bibitem{Lep14} \by V.~V.~Lepin \paper Algorithms for finding an independent $\{K_1,K_2\}$-packing of maximum weight in a graph \jour Tr. Inst. Mat. \yr 2014 \vol 22 \issue 1 \pages 78--97 \mathnet{http://mi.mathnet.ru/timb210} 

• http://mi.mathnet.ru/eng/timb210
• http://mi.mathnet.ru/eng/timb/v22/i1/p78

 SHARE:

Citing articles on Google Scholar: Russian citations, English citations
Related articles on Google Scholar: Russian articles, English articles

This publication is cited in the following articles:
1. V. V. Lepin, “Reshenie zadachi o vzveshennoi nezavisimoi $\{K_1,K_2\}$-upakovke na grafakh s ogranichennoi drevesnoi shirinoi”, Tr. In-ta matem., 23:1 (2015), 98–114
2. V. V. Lepin, “Reshenie zadachi o vzveshennoi nezavisimoi $\{K_1,K_2\}$-upakovke na grafakh so spetsialnymi blokami”, Tr. In-ta matem., 23:2 (2015), 62–71
3. V. V. Lepin, “Vzveshennaya zadacha o pokrytii $k$-tsepei posledovatelno-parallelnogo grafa”, Tr. In-ta matem., 25:1 (2017), 62–81
•  Number of views: This page: 211 Full text: 80 References: 18