Zobrazeno 1 - 10
of 155
pro vyhledávání: '"A, Limouzy"'
Autor:
Beaudou, Laurent, Bergé, Pierre, Chernyshev, Vsevolod, Dailly, Antoine, Gerard, Yan, Lagoutte, Aurélie, Limouzy, Vincent, Pastor, Lucas
We study the PSPACE-complete $k$-Canadian Traveller Problem, where a weighted graph $G=(V,E,\omega)$ with a source $s\in V$ and a target $t\in V$ are given. This problem also has a hidden input $E_* \subsetneq E$ of cardinality at most $k$ representi
Externí odkaz:
http://arxiv.org/abs/2403.01872
A set of vertices in a graph forms a potential maximal clique if there exists a minimal chordal completion in which it is a maximal clique. Potential maximal cliques were first introduced as a key tool to obtain an efficient, though exponential-time
Externí odkaz:
http://arxiv.org/abs/2402.18265
Autor:
Brosse, Caroline, Defrain, Oscar, Kurita, Kazuhiro, Limouzy, Vincent, Uno, Takeaki, Wasa, Kunihiro
Enumeration problems are often encountered as key subroutines in the exact computation of graph parameters such as chromatic number, treewidth, or treedepth. In the case of treedepth computation, the enumeration of inclusion-wise minimal separators p
Externí odkaz:
http://arxiv.org/abs/2308.15444
Publikováno v:
Discrete Mathematics & Theoretical Computer Science, vol. 25:3 special issue ICGT'22, Special issues (May 17, 2024) dmtcs:10805
This paper is devoted to the study of particular geometrically defined intersection classes of graphs. Those were previously studied by Magnant and Martin, who proved that these graphs have arbitrary large chromatic number, while being triangle-free.
Externí odkaz:
http://arxiv.org/abs/2301.03865
A poset is a containment of paths in a tree (CPT) if it admits a representation by containment where each element of the poset is represented by a path in a tree and two elements are comparable in the poset if and only if the corresponding paths are
Externí odkaz:
http://arxiv.org/abs/2204.04729
Publikováno v:
Discrete Mathematics & Theoretical Computer Science, Vol vol. 25:3 special issue..., Iss Special issues (2024)
This paper is devoted to the study of particular geometrically defined intersection classes of graphs. Those were previously studied by Magnant and Martin, who proved that these graphs have arbitrary large chromatic number, while being triangle-free.
Externí odkaz:
https://doaj.org/article/7dfb167fcb59446a8547848730ebc522
Autor:
Beaudou, Laurent, Brosse, Caroline, Defrain, Oscar, Foucaud, Florent, Lagoutte, Aurélie, Limouzy, Vincent, Pastor, Lucas
Publikováno v:
Discrete Mathematics & Theoretical Computer Science, vol. 25:2, Graph Theory (April 2, 2024) dmtcs:8715
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:
http://arxiv.org/abs/2110.14003
Motivated by the problem of enumerating all tree decompositions of a graph, we consider in this article the problem of listing all the minimal chordal completions of a graph. In \cite{carmeli2020} (\textsc{Pods 2017}) Carmeli \emph{et al.} proved tha
Externí odkaz:
http://arxiv.org/abs/2107.05972
Publikováno v:
In Discrete Applied Mathematics 15 March 2024 345:34-51
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