Zobrazeno 1 - 10
of 11
pro vyhledávání: '"Laurent Rosaz"'
Autor:
Leandro Montero, Zsolt Tuza, Csilia Bujtás, Hakim El Maftouhi, Laurent Rosaz, N. Narayanan, Johan Thapper, Marek Karpinski, Yannis Manoussakis, Jean Alexandre Anglés D’Auriac
Publikováno v:
WALCOM: Algorithms and Computation ISBN: 9783319301389
WALCOM
WALCOM
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
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::635d51f5a2c1410a50d34412c72295ce
https://doi.org/10.1007/978-3-319-30139-6_2
https://doi.org/10.1007/978-3-319-30139-6_2
Autor:
Zsolt Tuza, Jean Alexandre Anglés D’Auriac, Laurent Rosaz, Csilia Bujtás, N. Narayanan, Marek Karpinski, Yannis Manoussakis, Johan Thapper, Hakim El Maftouhi, Leandro Montero
Publikováno v:
Journal of Discrete Algorithms
Journal of Discrete Algorithms, Elsevier, 2018
Journal of Discrete Algorithms, Elsevier, 2018
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
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::fac14a678ae106dbd198fa4911adb687
http://arxiv.org/abs/1503.01008
http://arxiv.org/abs/1503.01008
Autor:
Laurent Rosaz
Publikováno v:
Theoretical Computer Science. 306:245-268
In this paper, it is proved that the word problem for congruences generated by subsets of {(abc,acb)|a∈A∪{ε},b,c∈A} is NP-hard. These congruences are a generalization of Mazurkiewicz's traces.
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::8624ee0ade259b01a5a33b5e27cb3e0d
https://doi.org/10.1016/s0304-3975(03)00283-4
https://doi.org/10.1016/s0304-3975(03)00283-4
Autor:
Laurent Rosaz
Publikováno v:
Theoretical Computer Science. 201(1-2):151-170
A language X on an alphabet A is unavoidable iff all but finitely many words in A ∗ have a factor in X. In this paper, I prove that the inventory of unavoidable languages of n words can be explicitly made for every n, that the reduced unavoidable l
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::f206c352d35b64b7bcfcd0e0acf0a45d
Autor:
Laurent Rosaz
Publikováno v:
RAIRO - Theoretical Informatics and Applications. 29:339-382
A language X on an alphabet A is unavoidable iff all but finitely many words in A * have a factor in X. In this paper, cuts (which are basically simplifications of languages in terms of avoidability) and innocent language (those which cannot be cut)
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::2b334237204943bc5c4acfadadd68cfd
https://doi.org/10.1051/ita/1995290503391
https://doi.org/10.1051/ita/1995290503391
Publikováno v:
Lecture Notes in Computer Science ISBN: 9783642354755
OPODIS
OPODIS
In this paper we show that, in terms of generated output languages, non-deterministic population protocols are strictly more powerful than deterministic ones. Analyzing the reason for this negative result, we propose two slightly enhanced models, in
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::f2fe6e055738cb28089f7cf7bfbe00b7
https://doi.org/10.1007/978-3-642-35476-2_5
https://doi.org/10.1007/978-3-642-35476-2_5
Autor:
Gerard Lallement, Laurent Rosaz
Publikováno v:
Semigroup Forum. 48:169-179
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::535cb96e1ad80b413a5f31a4d85d4f91
https://doi.org/10.1007/bf02573667
https://doi.org/10.1007/bf02573667
Publikováno v:
Lecture Notes in Computer Science ISBN: 9783540751410
DISC
DISC
Distributed computing must adapt its techniques to networks of mobile agents. Indeed, we are facing new problems like the small size of memory and the lack of computational power. In this paper, we extend the results of Angluin et al (see [4,3,2,1])
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::21b2e5518c7e8a02ab3392ef8d3ca729
https://doi.org/10.1007/978-3-540-75142-7_8
https://doi.org/10.1007/978-3-540-75142-7_8
Publikováno v:
PODC
Distributed computing has to adapt its techniques to mobile sensor networks and cope with constraints like small memory size or lack of computation power. In this paper we extend the results of Angluin et al (see [1,2,3,4]) by finding self-stabilizin
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::91aa5222da42ed88f69aaedc989f23c1
https://doi.org/10.1145/1281100.1281191
https://doi.org/10.1145/1281100.1281191
Autor:
Laurent Rosaz
Publikováno v:
PODC
In [2], J. Beauquier, M. Gradinariu and C. Johnen presented a probabilistic self-stabilizing token circulation algorithm for asynchronous uniform unidirectional rings. This paper provides an improvement on this algorithm. It also computes the (messag
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::04fdc84e801c1ebe8e85cd944ea7213a
https://doi.org/10.1145/343477.343626
https://doi.org/10.1145/343477.343626