J. -A. Angles D'Auriac
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Research Subjects
Research Interests
J. -A. Angles D'Auriac has a total of 9 co-authors. Here are the top co-authors by number of shared publications:
- A. El Maftouhi
Université Paris-Sud, L.R.I Bât. 650 91405 Orsay Cedex France
1 shared publication Cs. Bujtas
Department of Computer Science and Systems Technology University of Pannonia Egyetem u. 10 8200 Veszprém Hungary
1 shared publication- Johan Thapper
Universite Paris-Est Marne-la-Vallee France
1 shared publication - L. Rosaz
Université Paris-Sud, L.R.I Bât. 650 91405 Orsay Cedex France
1 shared publication - Leandro Montero
Laboratoire de Recherche en Informatique Université Paris-Sud 91405 Orsay CEDEX France
1 shared publication - Marek Karpinski
Univ Bonn, Dept Comp Sci, Bonn, Germany
1 shared publication
Latest Publications
- Open Access
Tropical Dominating Sets in Vertex-Coloured Graphs
Given a vertex-coloured graph, a dominating set is said to be tropical if every colour of the graph appears at least once in the set. Here, we study minimum tropical dominating sets from structural and algorithmic points of view. First, we prove that the tropical dominating set problem is NP-complete even when restricted to a simple path. Then, we establish upper bounds related to various parameters of the graph such as minimum degree and number of edges. We also give upper bounds for random graphs. Last, we give approximability and inapproximability results for general and restricted classes of graphs, and establish a FPT algorithm for interval graphs.
Open AccessTropical Dominating Sets in Vertex-Coloured Graphs
Given a vertex-coloured graph, a dominating set is said to be tropical if every colour of the graph appears at least once in the set. Here, we study minimum tropical dominating sets from structural and algorithmic points of view. First, we prove that the tropical dominating set problem is NP-complete even when restricted to a simple path. Then, we establish upper bounds related to various parameters of the graph such as minimum degree and number of edges. We also give upper bounds for random graphs. Last, we give approximability and inapproximability results for general and restricted classes of graphs, and establish a FPT algorithm for interval graphs.