Complete-Subgraph-Transversal-Sets problem on bounded treewidth graphs
Complete-Subgraph-Transversal-Sets problem on bounded treewidth graphs
复制标题
有界树宽图上的完全子图横向集问题
DOI：
10.1007/s10878-021-00703-7
复制
发表时间：
2021-05
影响因子：
1
通讯作者：
Mei Lu
中科院分区：
文献类型：
--
作者：
Ke Liu;Mei Lu
让我们做个图表。G的完全子图是V的两两相邻顶点的大小至少为2的子图。设为Gand的所有完全子图的集合。本文研究了完全子图横截集问题和L-Max完全子图横截集问题。我们给多项式时间算法，这两个问题的图有界树宽。 最后，我们还讨论了这两个问题与其它NP完全问题的联系，如图的C-T-集问题和超图的顶点覆盖问题。
Letbe a graph. A complete subgraph ofGis a subgraph of pairwise adjacent vertices ofVof size at least 2. Letbe the set of all complete subgraphs ofGand. In this paper, we consider the Complete-Subgraph-Transversal-Set onproblem and theL-Max Complete-Subgraph-Transversal-Set onproblem. We give polynomial time algorithms to these two problems on graphs of bounded treewidth. At last, we show the connections between these two problems with some other NP-complete problems, for example Clique-Transversal-Set problem on graphs and Vertex-Cover problem on hypergraphs.
登录
查看更多内容
DOI：
10.1016/0012-365x(90)90354-k
发表时间：
1991-01
期刊：
Discret. Math.
影响因子：
--
作者：
Z. Tuza
通讯作者：
Z. Tuza
DOI：
10.1016/0012-365x(92)90681-5
发表时间：
1992-10
期刊：
Discret. Math.
影响因子：
--
作者：
P. Erdös;T. Gallai;Z. Tuza
通讯作者：
P. Erdös;T. Gallai;Z. Tuza
DOI：
10.1016/j.cosrev.2007.09.001
发表时间：
2007-12
期刊：
Comput. Sci. Rev.
影响因子：
--
作者：
D. Thilikos
通讯作者：
D. Thilikos
影响因子：
1.1
作者：
J. Alber;H. Bodlaender;H. Fernau;T. Kloks;R. Niedermeier
通讯作者：
J. Alber;H. Bodlaender;H. Fernau;T. Kloks;R. Niedermeier
DOI：
10.1145/167088.167161
发表时间：
1993-06
期刊：
Proceedings of the twenty-fifth annual ACM symposium on Theory of Computing
影响因子：
--
作者：
H. Bodlaender
通讯作者：
H. Bodlaender