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., 2014, Volume 22, Number 1, Pages 78–97 (Mi timb210)  

This article is cited in 3 scientific papers (total in 3 papers)

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

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}


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

    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, “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  mathnet
    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  mathnet
    3. 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:211
    Full text:80
    References:18

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