Zobrazeno 1 - 8
of 8
pro vyhledávání: '"Sayadi, Mohamed Yosri"'
Autor:
Sayadi, Mohamed Yosri
The enumeration of minimal connected dominating sets is known to be notoriously hard for general graphs. Currently, it is only known that the sets can be enumerated slightly faster than $\mathcal{O}^{*}(2^n)$ and the algorithm is highly nontrivial. M
Externí odkaz:
http://arxiv.org/abs/1908.02174
Publikováno v:
In Theoretical Computer Science 6 September 2019 783:41-52
Publikováno v:
In Discrete Applied Mathematics 31 July 2019 265:69-85
Publikováno v:
In Theoretical Computer Science 6 January 2019 754:3-15
Autor:
Sayadi, Mohamed Yosri
Publikováno v:
Informatique [cs]. Université de Lorraine, 2019. Français. ⟨NNT : 2019LORR0316⟩
Moon and Moser proved that the maximum number of maximal independent sets in a graph of n vertices is at most 3^{n/3}. This maximum number, called upper bound, is tight given the existence of a family of graphs with such a number called lower bound.
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=dedup_wf_001::a9b6b697d16df4ff60c2efd90931a0b2
https://hal.univ-lorraine.fr/tel-02860933
https://hal.univ-lorraine.fr/tel-02860933
Autor:
Sayadi, Mohamed Yosri
Moon and Moser proved that the maximum number of maximal independent sets in a graph of n vertices is at most 3^{n/3}. This maximum number, called upper bound, is tight given the existence of a family of graphs with such a number called lower bound.
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=od______2592::a9b6b697d16df4ff60c2efd90931a0b2
https://hal.univ-lorraine.fr/tel-02860933
https://hal.univ-lorraine.fr/tel-02860933
Publikováno v:
SOFSEM 2017: Theory & Practice of Computer Science; 2017, p217-228, 12p
Publikováno v:
Lecture Notes in Computer Science; 2017, p289-302, 14p