Zobrazeno 1 - 10
of 59
pro vyhledávání: '"P. 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
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
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
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
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
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
In this paper, we are interested in algorithms that take in input an arbitrary graph $G$, and that enumerate in output all the (inclusion-wise) maximal "subgraphs" of $G$ which fulfil a given property $\Pi$. All over this paper, we study several diff
Externí odkaz:
http://arxiv.org/abs/2007.01031