Non-monotone target sets for threshold values restricted to $0$, $1$, and the vertex degree

Autor: Julien Baste, Stefan Ehard, Dieter Rautenbach

Publikováno v: Discrete Mathematics & Theoretical Computer Science, Vol vol. 24, no. 1, Iss Graph Theory (2022)

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: https://doaj.org/article/4be6ebdcfd9b424182695b475fe84d99

Towards hybridization of multi-agent simulation and metaheuristics applied to selective deconstruction

Autor: Corentin Juvigny, Julien Baste, Guillaume Lozenguez, Arnaud Doniec, Laetitia Jourdan

Publikováno v: 2022 IEEE Symposium Series on Computational Intelligence (SSCI)
2022 IEEE Symposium Series on Computational Intelligence (SSCI), Dec 2022, Singapore, Singapore. pp.767-773, ⟨10.1109/SSCI51031.2022.10022117⟩

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::0c09124d02564a41e0886a1e5ffce067
https://doi.org/10.1109/ssci51031.2022.10022117

Diversity of solutions: An exploration through the lens of fixed-parameter tractability theory

Autor: Michael R. Fellows, Frances A. Rosamond, Julien Baste, Mateus de Oliveira Oliveira, Lars Jaffke, Geevarghese Philip, Tomáš Masařík

Publikováno v: Artificial Intelligence
Artificial Intelligence, 2022, 303, pp.103644. ⟨10.1016/j.artint.2021.103644⟩
Artificial Intelligence, Elsevier, 2022, 303, pp.103644. ⟨10.1016/j.artint.2021.103644⟩
IJCAI
Twenty-Ninth International Joint Conference on Artificial Intelligence and Seventeenth Pacific Rim International Conference on Artificial Intelligence {IJCAI-PRICAI-20}
Twenty-Ninth International Joint Conference on Artificial Intelligence and Seventeenth Pacific Rim International Conference on Artificial Intelligence, Jul 2020, Yokohama, Japan. pp.1119-1125, ⟨10.24963/ijcai.2020/156⟩
Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence

When modeling an application of practical relevance as an instance of a combinatorial problem X, we are often interested not merely in finding one optimal solution for that instance, but in finding a sufficiently diverse collection of good solutions.

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::adf19510b9f6c7ba32d99cbdf89ea227
https://hal.science/hal-03469328

Hitting minors on bounded treewidth graphs. III. Lower bounds

Autor: Ignasi Sau, Julien Baste, Dimitrios M. Thilikos

Publikováno v: Journal of Computer and System Sciences
Journal of Computer and System Sciences, Elsevier, 2020, 109, pp.56-77. ⟨10.1016/j.jcss.2019.11.002⟩

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: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::d99f57921ee0a711a3f8eff26d78adce

Domination versus edge domination

Autor: Michael A. Henning, Elena Mohr, Dieter Rautenbach, Maximilian Fürst, Julien Baste

Publikováno v: Discrete Applied Mathematics
Discrete Applied Mathematics, Elsevier, 2020, 285, pp.343-349. ⟨10.1016/j.dam.2020.05.030⟩

We propose the conjecture that the domination number γ ( G ) of a Δ -regular graph G with Δ ≥ 1 is always at most its edge domination number γ e ( G ) , which coincides with the domination number of its line graph. We prove that γ ( G ) ≤ 1

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::9cc741948a5acaafa135aab5fb3c7102
https://hal.archives-ouvertes.fr/hal-03470076