Geodesic
An improved algorithm for the vertex cover $P_3$ problem on graphs of bounded treewidth
Discrete mathematics & theoretical computer science, Tome 21 (2019) no. 4.

Voir la notice de l'article provenant de la source Episciences

Given a graph $G=(V,E)$ and a positive integer $t\geq2$, the task in the vertex cover $P_t$ ($VCP_t$) problem is to find a minimum subset of vertices $F\subseteq V$ such that every path of order $t$ in $G$ contains at least one vertex from $F$. The $VCP_t$ problem is NP-complete for any integer $t\geq2$ and has many applications in real world. Recently, the authors presented a dynamic programming algorithm running in time $4^p\cdot n^{O(1)}$ for the $VCP_3$ problem on $n$-vertex graphs with treewidth $p$. In this paper, we propose an improvement of it and improved the time-complexity to $3^p\cdot n^{O(1)}$. The connected vertex cover $P_3$ ($CVCP_3$) problem is the connected variation of the $VCP_3$ problem where $G[F]$ is required to be connected. Using the Cut\&Count technique, we give a randomized algorithm with runtime $4^p\cdot n^{O(1)}$ for the $CVCP_3$ problem on $n$-vertex graphs with treewidth $p$. 
@article{DMTCS_2019_21_4_a15,
     author = {Bai, Zongwen and Tu, Jianhua and Shi, Yongtang},
     title = {An improved algorithm for the vertex cover $P_3$ problem on graphs of bounded treewidth},
     journal = {Discrete mathematics & theoretical computer science},
     publisher = {mathdoc},
     volume = {21},
     number = {4},
     year = {2019},
     doi = {10.23638/DMTCS-21-4-17},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.23638/DMTCS-21-4-17/}
}
TY  - JOUR
AU  - Bai, Zongwen
AU  - Tu, Jianhua
AU  - Shi, Yongtang
TI  - An improved algorithm for the vertex cover $P_3$ problem on graphs of bounded treewidth
JO  - Discrete mathematics & theoretical computer science
PY  - 2019
VL  - 21
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.23638/DMTCS-21-4-17/
DO  - 10.23638/DMTCS-21-4-17
LA  - en
ID  - DMTCS_2019_21_4_a15
ER  - 
%0 Journal Article
%A Bai, Zongwen
%A Tu, Jianhua
%A Shi, Yongtang
%T An improved algorithm for the vertex cover $P_3$ problem on graphs of bounded treewidth
%J Discrete mathematics & theoretical computer science
%D 2019
%V 21
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.23638/DMTCS-21-4-17/
%R 10.23638/DMTCS-21-4-17
%G en
%F DMTCS_2019_21_4_a15
Bai, Zongwen; Tu, Jianhua; Shi, Yongtang. An improved algorithm for the vertex cover $P_3$ problem on graphs of bounded treewidth. Discrete mathematics & theoretical computer science, Tome 21 (2019) no. 4. doi : 10.23638/DMTCS-21-4-17. http://geodesic.mathdoc.fr/articles/10.23638/DMTCS-21-4-17/

Cité par Sources :