Geodesic
Connected Tropical Subgraphs in Vertex-Colored Graphs
Discrete mathematics & theoretical computer science, Tome 17 (2015-2016) no. 3 Cet article a éte moissonné depuis la source Episciences

Voir la notice de l'article

A subgraph of a vertex-colored graph is said to be tropical whenever it contains each color of the graph. In this work we study the problem of finding a minimal connected tropical subgraph. We first show that this problem is NP-Hard for trees, interval graphs and split graphs, but polynomial when the number of colors is logarithmic in terms of the order of the graph (i.e. FPT). We then provide upper bounds for the order of the minimal connected tropical subgraph under various conditions. We finally study the problem of finding a connected tropical subgraph in a randomly vertex-colored random graph. 
@article{DMTCS_2016_17_3_a7,
     author = {Angl\`es d'Auriac, Jean-Alexandre and Cohen, Nathann and El Mafthoui, Hakim and Harutyunyan, Ararat and Legay, Sylvain and Manoussakis, Yannis},
     title = {Connected {Tropical} {Subgraphs} in {Vertex-Colored} {Graphs}},
     journal = {Discrete mathematics & theoretical computer science},
     year = {2015-2016},
     volume = {17},
     number = {3},
     doi = {10.46298/dmtcs.2151},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.2151/}
}
TY  - JOUR
AU  - Anglès d'Auriac, Jean-Alexandre
AU  - Cohen, Nathann
AU  - El Mafthoui, Hakim
AU  - Harutyunyan, Ararat
AU  - Legay, Sylvain
AU  - Manoussakis, Yannis
TI  - Connected Tropical Subgraphs in Vertex-Colored Graphs
JO  - Discrete mathematics & theoretical computer science
PY  - 2015-2016
VL  - 17
IS  - 3
UR  - http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.2151/
DO  - 10.46298/dmtcs.2151
LA  - en
ID  - DMTCS_2016_17_3_a7
ER  - 
%0 Journal Article
%A Anglès d'Auriac, Jean-Alexandre
%A Cohen, Nathann
%A El Mafthoui, Hakim
%A Harutyunyan, Ararat
%A Legay, Sylvain
%A Manoussakis, Yannis
%T Connected Tropical Subgraphs in Vertex-Colored Graphs
%J Discrete mathematics & theoretical computer science
%D 2015-2016
%V 17
%N 3
%U http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.2151/
%R 10.46298/dmtcs.2151
%G en
%F DMTCS_2016_17_3_a7
Anglès d'Auriac, Jean-Alexandre; Cohen, Nathann; El Mafthoui, Hakim; Harutyunyan, Ararat; Legay, Sylvain; Manoussakis, Yannis. Connected Tropical Subgraphs in Vertex-Colored Graphs. Discrete mathematics & theoretical computer science, Tome 17 (2015-2016) no. 3. doi: 10.46298/dmtcs.2151

Cité par Sources :