Zobrazeno 1 - 10
of 10
pro vyhledávání: '"Oscar Defrain"'
Autor:
Laurent Beaudou, Caroline Brosse, Oscar Defrain, Florent Foucaud, Aurélie Lagoutte, Vincent Limouzy, Lucas Pastor
Publikováno v:
Discrete Mathematics & Theoretical Computer Science, Vol vol. 25:2, Iss Graph Theory (2024)
The Grundy number of a graph is the maximum number of colours used by the "First-Fit" greedy colouring algorithm over all vertex orderings. Given a vertex ordering $\sigma= v_1,\dots,v_n$, the "First-Fit" greedy colouring algorithm colours the vertic
Externí odkaz:
https://doaj.org/article/a885163b95d94d1d87168b84ee0b63b8
Publikováno v:
Discrete Mathematics
Discrete Mathematics, Elsevier, 2021, 344 (7), pp.112399. ⟨10.1016/j.disc.2021.112399⟩
Discrete Mathematics, 2021, 344 (7), pp.112399. ⟨10.1016/j.disc.2021.112399⟩
Discrete Mathematics, Elsevier, 2021, 344 (7), pp.112399. ⟨10.1016/j.disc.2021.112399⟩
Discrete Mathematics, 2021, 344 (7), pp.112399. ⟨10.1016/j.disc.2021.112399⟩
It is well known that every closure system can be represented by an implicational base, or by the set of its meet-irreducible elements. In Horn logic, these are respectively known as the Horn expressions and the characteristic models. In this paper,
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::2fa3ce267a0f759d8759d3415c678c00
https://hal.archives-ouvertes.fr/hal-03354987
https://hal.archives-ouvertes.fr/hal-03354987
Autor:
Lhouari Nourine, Oscar Defrain
Publikováno v:
Theoretical Computer Science
Theoretical Computer Science, Elsevier, 2020, 814, pp.169-176. ⟨10.1016/j.tcs.2020.01.028⟩
Theoretical Computer Science, 2020, 814, pp.169-176. ⟨10.1016/j.tcs.2020.01.028⟩
Theoretical Computer Science, Elsevier, 2020, 814, pp.169-176. ⟨10.1016/j.tcs.2020.01.028⟩
Theoretical Computer Science, 2020, 814, pp.169-176. ⟨10.1016/j.tcs.2020.01.028⟩
It was recently proved that the dualization in lattices given by implicational bases is impossible in output-polynomial time unless P=NP. In this paper, we~show that this result holds even when the premises in the implicational base are of size at mo
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::b7ea8707c48d49ba571d91c0060a16d6
https://hal.archives-ouvertes.fr/hal-03181679
https://hal.archives-ouvertes.fr/hal-03181679
Publikováno v:
The Electronic Journal of Combinatorics
We prove a recent conjecture of Beisegel et al. that for every positive integer k, every graph containing an induced P_k also contains an avoidable P_k. Avoidability generalises the notion of simpliciality best known in the context of chordal graphs.
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::d0e1ea27a6f839ec68ba3ef0a071f71a
Autor:
Oscar Defrain, Jean-Sébastien Sereni, Pierre Charbit, Aurélie Lagoutte, Lucas Pastor, Marthe Bonamy, Gwenaël Joret, Vincent Limouzy
Publikováno v:
The electronic journal of combinatorics, 27 (1
The Electronic Journal of Combinatorics
The Electronic Journal of Combinatorics, Open Journal Systems, 2020, 27 (1), pp.P1.56. ⟨10.37236/8899⟩
The Electronic Journal of Combinatorics, 2020, 27 (1), pp.P1.56. ⟨10.37236/8899⟩
The Electronic Journal of Combinatorics
The Electronic Journal of Combinatorics, Open Journal Systems, 2020, 27 (1), pp.P1.56. ⟨10.37236/8899⟩
The Electronic Journal of Combinatorics, 2020, 27 (1), pp.P1.56. ⟨10.37236/8899⟩
We give a short proof of the following theorem due to Jon H. Folkman (1969): The chromatic number of any graph is at most 2 plus the maximum over all subgraphs of the difference between the number of vertices and twice the independence number.
S
S
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::3f819feba2ca2b69090ca69dd4557d24
https://hal.archives-ouvertes.fr/hal-02194900
https://hal.archives-ouvertes.fr/hal-02194900
Publikováno v:
Discrete Applied Mathematics
Discrete Applied Mathematics, 2021, 300, pp.85-96. ⟨10.1016/j.dam.2021.04.018⟩
Discrete Applied Mathematics, 2021, 300, pp.85-96. ⟨10.1016/j.dam.2021.04.018⟩
In this paper, we study the dualization in distributive lattices, a generalization of the well-known hypergraph dualization problem. We in particular propose equivalent formulations of the problem in terms of graphs, hypergraphs, and posets. It is kn
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::b4676ea4cfb5bde42d51cea965baa88c
Autor:
Lhouari Nourine, Oscar Defrain
Publikováno v:
Formal Concept Analysis ISBN: 9783030214616
ICFCA
ICFCA
It was recently proved that the dualization in lattices given by implicational bases is impossible in output-polynomial time unless \(\mathsf{P}\!=\!\mathsf{NP}\). In this paper, we show that this result holds even when the premises in the implicatio
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::1fc4b5b63dd8fc173cc77c49fe49bf91
https://doi.org/10.1007/978-3-030-21462-3_7
https://doi.org/10.1007/978-3-030-21462-3_7
Publikováno v:
13th Conference on Computability in Europe
CiE: Conference on Computability in Europe
CiE: Conference on Computability in Europe, Jun 2017, Turku, Finland. pp.221-233, ⟨10.1007/978-3-319-58741-7_22⟩
Unveiling Dynamics and Complexity ISBN: 9783319587400
CiE
CiE 2017-13th Conference on Computability in Europe
CiE 2017-13th Conference on Computability in Europe, Jun 2017, Turku, Finland. pp.221-233, ⟨10.1007/978-3-319-58741-7_22⟩
CiE: Conference on Computability in Europe
CiE: Conference on Computability in Europe, Jun 2017, Turku, Finland. pp.221-233, ⟨10.1007/978-3-319-58741-7_22⟩
Unveiling Dynamics and Complexity ISBN: 9783319587400
CiE
CiE 2017-13th Conference on Computability in Europe
CiE 2017-13th Conference on Computability in Europe, Jun 2017, Turku, Finland. pp.221-233, ⟨10.1007/978-3-319-58741-7_22⟩
International audience; In 1962, Hungarian mathematician Tibor Radó introduced in [8] the busy beaver competition for Turing machines: in a class of machines, find one which halts after the greatest number of steps when started on the empty input. I
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::e0de94ddda8fbb9b4ac03b6feed91220
https://hal-lirmm.ccsd.cnrs.fr/lirmm-02096207
https://hal-lirmm.ccsd.cnrs.fr/lirmm-02096207
Publikováno v:
Journal of Combinatorial Theory, Series B
Journal of Combinatorial Theory, Series B, In press, ⟨10.1016/j.jctb.2022.07.009⟩
Journal of Combinatorial Theory, Series B, In press, ⟨10.1016/j.jctb.2022.07.009⟩
Tree-cut width is a graph parameter introduced by Wollan that is an analogue of treewidth for the immersion order on graphs in the following sense: the tree-cut width of a graph is functionally equivalent to the largest size of a wall that can be fou
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::e184044aeba9985914a8faad093509af
Publikováno v:
ACM Transactions on Algorithms
ACM Transactions on Algorithms, 2020, 16 (3), pp.1-23. ⟨10.1145/3386686⟩
ACM Transactions on Algorithms, Association for Computing Machinery, 2020, 16 (3), pp.1-23. ⟨10.1145/3386686⟩
ACM Transactions on Algorithms, 2020, 16 (3), pp.1-23. ⟨10.1145/3386686⟩
ACM Transactions on Algorithms, Association for Computing Machinery, 2020, 16 (3), pp.1-23. ⟨10.1145/3386686⟩
It is a long-standing open problem whether the minimal dominating sets of a graph can be enumerated in output-polynomial time. In this paper we investigate this problem in graph classes defined by forbidding an induced subgraph. In particular, we pro
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::b5a44b9b6c30df12811c864b5daab614