Connected Tropical Subgraphs in Vertex-Colored Graphs

Abstract : 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.
Type de document :
Article dans une revue
Discrete Mathematics and Theoretical Computer Science, DMTCS, 2016, Vol. 17 no. 3 (3), pp.327-348
Liste complète des métadonnées

Littérature citée [17 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01352845
Contributeur : Coordination Episciences Iam <>
Soumis le : mercredi 17 août 2016 - 11:36:03
Dernière modification le : jeudi 5 avril 2018 - 12:30:09
Document(s) archivé(s) le : vendredi 18 novembre 2016 - 10:06:53

Fichier

2765-9988-2-PB.pdf
Accord explicite pour ce dépôt

Identifiants

  • HAL Id : hal-01352845, version 1

Citation

Jean-Alexandre Anglès d'Auriac, Nathann Cohen, Hakim El Mafthoui, Ararat Harutyunyan, Sylvain Legay, et al.. Connected Tropical Subgraphs in Vertex-Colored Graphs. Discrete Mathematics and Theoretical Computer Science, DMTCS, 2016, Vol. 17 no. 3 (3), pp.327-348. 〈hal-01352845〉

Partager

Métriques

Consultations de la notice

253

Téléchargements de fichiers

119