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






Personal entry:
Login:
Password:
Save password
Enter
Forgotten password?
Register


Tr. Inst. Mat., 2015, Volume 23, Number 2, Pages 62–71 (Mi timb242)  

This article is cited in 1 scientific paper (total in 1 paper)

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
Received: 10.10.2015

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}


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

    SHARE: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru


    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  mathnet
  • Труды Института математики
    Number of views:
    This page:133
    Full text:50
    References:20

     
    Contact us:
     Terms of Use  Registration  Logotypes © Steklov Mathematical Institute RAS, 2020