Zobrazeno 1 - 10
of 122
pro vyhledávání: '"Baste, Julien"'
Autor:
Baste, Julien
In the Fully Leafed Induced Subtrees, one is given a graph $G$ and two integers $a$ and $b$ and the question is to find an induced subtree of $G$ with $a$ vertices and at least $b$ leaves. This problem is known to be NP-complete even when the input g
Externí odkaz:
http://arxiv.org/abs/2301.12783
Autor:
Baste, Julien, Thilikos, Dimitrios M.
Given a graph $G$, we define ${\bf bcg}(G)$ as the minimum $k$ for which $G$ can be contracted to the uniformly triangulated grid $\Gamma_{k}$. A graph class ${\cal G}$ has the SQG${\bf C}$ property if every graph $G\in{\cal G}$ has treewidth $\mathc
Externí odkaz:
http://arxiv.org/abs/2207.09751
Publikováno v:
In Theoretical Computer Science 27 November 2024 1018
Autor:
Baste, Julien, Watel, Dimitri
Publikováno v:
In Theoretical Computer Science 1 April 2024 990
For a finite collection of graphs ${\cal F}$, the ${\cal F}$-M-DELETION problem consists in, given a graph $G$ and an integer $k$, decide whether there exists $S \subseteq V(G)$ with $|S| \leq k$ such that $G \setminus S$ does not contain any of the
Externí odkaz:
http://arxiv.org/abs/2103.06614
For a finite collection of graphs ${\cal F}$, the ${\cal F}$-M-DELETION (resp. ${\cal F}$-TM-DELETION) problem consists in, given a graph $G$ and an integer $k$, decide whether there exists $S \subseteq V(G)$ with $|S| \leq k$ such that $G \setminus
Externí odkaz:
http://arxiv.org/abs/2103.06536
We introduce in this paper a new summarization method for large graphs. Our summarization approach retains only a user-specified proportion of the neighbors of each node in the graph. Our main aim is to simplify large graphs so that they can be analy
Externí odkaz:
http://arxiv.org/abs/2101.11559
Autor:
Baste, Julien1
Publikováno v:
Discrete Mathematics & Theoretical Computer Science (DMTCS). 2024, Vol. 26 Issue 2, p1-16. 16p.
Publikováno v:
Discrete Mathematics & Theoretical Computer Science, vol. 24, no. 1, Graph Theory (May 13, 2022) dmtcs:6844
We consider a non-monotone activation process $(X_t)_{t\in\{ 0,1,2,\ldots\}}$ on a graph $G$, where $X_0\subseteq V(G)$, $X_t=\{ u\in V(G):|N_G(u)\cap X_{t-1}|\geq \tau(u)\}$ for every positive integer $t$, and $\tau:V(G)\to \mathbb{Z}$ is a threshol
Externí odkaz:
http://arxiv.org/abs/2007.03959
A matching $M$ in a graph $G$ is acyclic if the subgraph of $G$ induced by the set of vertices that are incident to an edge in $M$ is a forest. We prove that every graph with $n$ vertices, maximum degree at most $\Delta$, and no isolated vertex, has
Externí odkaz:
http://arxiv.org/abs/2002.03649