|
This article is cited in 1 scientific paper (total in 1 paper)
The complexity for the problems of covering of a graph with the minimum number of complete bipartite subgraphs
O. I. Duginov Institute of Mathematics of the National Academy of Sciences of Belarus
Abstract:
Problems of covering the vertex set (the edge set) of a simple graph with a minimum number of complete bipartite subgraphs are studied. We give a polynomial time algorithm for the first problem restricted to the class of $S_{1,2,3}$-free bipartite graphs, where $S_{1,2,3}$ is the graph with the vertex set $\{a,b,c,d,e,f,g\}$ and the edge set $\{ab,bc,cd,fe,ed,gd\}$. Besides we show that the first problem in the class of bipartite graphs cannot be approximated in polynomial time within a factor $\mathrm{const}\cdot\ln{n},$ where $n$ is the number of vertices of the given bipartite graph, unless $P=NP$. On the other hand, we give polynomial time greedy approximation algorithm within a factor $H_n$. Also we show that the second problem is NP-complete in the class of $(K_{3,4},K_{3,4}-e)$-free bipartite graphs with degrees at most 7.
Received: 02.02.2014
Citation:
O. I. Duginov, “The complexity for the problems of covering of a graph with the minimum number of complete bipartite subgraphs”, Tr. Inst. Mat., 22:1 (2014), 51–69
Linking options:
https://www.mathnet.ru/eng/timb208 https://www.mathnet.ru/eng/timb/v22/i1/p51
|
Statistics & downloads: |
Abstract page: | 509 | Full-text PDF : | 525 | References: | 45 |
|