On locating cubic subgraphs in bounded-degree connected bipartite graphs

被引：10
作者：
Stewart, IA [1 ]
机构：
[1] UNIV COLL SWANSEA,DEPT COMP SCI,SWANSEA SA2 8PP,W GLAM,WALES
来源：
DISCRETE MATHEMATICS | 1997年 / 163卷 / 1-3期
关键词：
computational complexity; cubic subgraphs; bounded-degree bipartite graphs;
D O I：
10.1016/0012-365X(95)00324-P
中图分类号：
O1 [数学];
学科分类号：
0701 ; 070101 ;
摘要：
We show that the problem of deciding whether a connected bipartite graph of degree at most 4 has a cubic subgraph is NP-complete.
引用
收藏
页码：319 / 324
页数：6
相关论文
共 5 条
1