solidot新版网站常见问题，请点击这里查看。
消息
本文已被查看4134次
Connected Vertex Cover for $(sP_1+P_5)$-Free Graphs. (arXiv:1712.08362v1 [cs.DS])
来源于:arXiv
The Connected Vertex Cover problem is to decide if a graph $G$ has a vertex
cover of size at most $k$ that induces a connected subgraph of $G$. A graph is
$H$-free if it does not contain $H$ as an induced subgraph. We prove that
Connected Vertex Cover is polynomial-time solvable for $(sP_1+P_5)$-free graphs
for all $s\geq 0$. 查看全文>>
