Geodesic
Total Domination, Connected Vertex Cover and Steiner Tree with Conflicts
Discrete mathematics & theoretical computer science, Tome 19 (2017-2018) no. 3.

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

Total dominating set, connected vertex cover and Steiner tree are well-known graph problems. Despite the fact that they are NP-complete to optimize, it is easy (even trivial) to find solutions, regardless of their size. In this paper, we study a variant of these problems by adding conflicts, that are pairs of vertices that cannot be both in a solution. This new constraint leads to situations where it is NP-complete to decide if there exists a solution avoiding conflicts. This paper proposes NP-completeness proofs of the existence of a solution for different restricted classes of graphs and conflicts, improving recent results. We also propose polynomial time constructions in several restricted cases and we introduce a new parameter, the stretch, to capture the locality of the conflicts. 
@article{DMTCS_2017_19_3_a15,
     author = {Cornet, Alexis and Laforest, Christian},
     title = {Total {Domination,} {Connected} {Vertex} {Cover} and {Steiner} {Tree} with {Conflicts}},
     journal = {Discrete mathematics & theoretical computer science},
     publisher = {mathdoc},
     volume = {19},
     number = {3},
     year = {2017-2018},
     doi = {10.23638/DMTCS-19-3-17},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.23638/DMTCS-19-3-17/}
}
TY  - JOUR
AU  - Cornet, Alexis
AU  - Laforest, Christian
TI  - Total Domination, Connected Vertex Cover and Steiner Tree with Conflicts
JO  - Discrete mathematics & theoretical computer science
PY  - 2017-2018
VL  - 19
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.23638/DMTCS-19-3-17/
DO  - 10.23638/DMTCS-19-3-17
LA  - en
ID  - DMTCS_2017_19_3_a15
ER  - 
%0 Journal Article
%A Cornet, Alexis
%A Laforest, Christian
%T Total Domination, Connected Vertex Cover and Steiner Tree with Conflicts
%J Discrete mathematics & theoretical computer science
%D 2017-2018
%V 19
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.23638/DMTCS-19-3-17/
%R 10.23638/DMTCS-19-3-17
%G en
%F DMTCS_2017_19_3_a15
Cornet, Alexis; Laforest, Christian. Total Domination, Connected Vertex Cover and Steiner Tree with Conflicts. Discrete mathematics & theoretical computer science, Tome 19 (2017-2018) no. 3. doi : 10.23638/DMTCS-19-3-17. http://geodesic.mathdoc.fr/articles/10.23638/DMTCS-19-3-17/

Cité par Sources :