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., 2015, Volume 23, Number 2, Pages 62–71 (Mi timb242)

Solving the problem of finding an independent $\{K_1,K_2\}$-packing of maximum weight on graphs with special blocks

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

 Funding Agency Grant Number Belarusian Republican Foundation for Fundamental Research Ô14ÐÀ-004Ô15ÌËÄ-022

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

Citation: V. V. Lepin, “Solving the problem of finding an independent $\{K_1,K_2\}$-packing of maximum weight on graphs with special blocks”, Tr. Inst. Mat., 23:2 (2015), 62–71

Citation in format AMSBIB
\Bibitem{Lep15} \by V.~V.~Lepin \paper Solving the problem of finding an independent $\{K_1,K_2\}$-packing of maximum weight on graphs with special blocks \jour Tr. Inst. Mat. \yr 2015 \vol 23 \issue 2 \pages 62--71 \mathnet{http://mi.mathnet.ru/timb242} 

• http://mi.mathnet.ru/eng/timb242
• http://mi.mathnet.ru/eng/timb/v23/i2/p62

 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, “Vzveshennaya zadacha o pokrytii $k$-tsepei posledovatelno-parallelnogo grafa”, Tr. In-ta matem., 25:1 (2017), 62–81
•  Number of views: This page: 133 Full text: 50 References: 20