Výsledky vyhledávání - "Rémy Belmonte"

Akademický článek

New Results on Directed Edge Dominating Set

Autor: Rémy Belmonte, Tesshu Hanaka, Ioannis Katsikarelis, Eun Jung Kim, Michael Lampis

Publikováno v: Discrete Mathematics & Theoretical Computer Science, Vol vol. 25:1 (2023)

We study a family of generalizations of Edge Dominating Set on directed graphs called Directed $(p,q)$-Edge Dominating Set. In this problem an arc $(u,v)$ is said to dominate itself, as well as all arcs which are at distance at most $q$ from $v$, or

Externí odkaz: https://doaj.org/article/804a99ed163d4f95b99b4ae8a732ba86

Zobrazit plný text záznamu

Akademický článek

Defective Coloring on Classes of Perfect Graphs

Autor: Rémy Belmonte, Michael Lampis, Valia Mitsou

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

In Defective Coloring we are given a graph $G$ and two integers $\chi_d$, $\Delta^*$ and are asked if we can $\chi_d$-color $G$ so that the maximum degree induced by any color class is at most $\Delta^*$. We show that this natural generalization of C

Externí odkaz: https://doaj.org/article/691d56501f4b4b898a299ceda7477164

Zobrazit plný text záznamu

Parameterized Complexity of $$(A,\ell )$$-Path Packing

Autor: Rémy Belmonte, Tesshu Hanaka, Masaaki Kanzaki, Masashi Kiyomi, Yasuaki Kobayashi, Yusuke Kobayashi, Michael Lampis, Hirotaka Ono, Yota Otachi

Publikováno v: Algorithmica. 84:871-895

Given a graph $$G = (V,E)$$ G = ( V , E ) , $$A \subseteq V$$ A ⊆ V , and integers k and $$\ell $$ ℓ , the $$(A,\ell )$$ ( A , ℓ ) -Path Packing problem asks to find k vertex-disjoint paths of length exactly $$\ell $$ ℓ that have endpoints in

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_________::8b0e3966aa3bca95111d9d6a5f9d6970
https://doi.org/10.1007/s00453-021-00875-y

Zobrazit plný text záznamu

K3 Edge Cover Problem in a Wide Sense

Autor: Kyohei Chiba, Rémy Belmonte, Hiro Ito, Atsuki Nagao, Michael Lampis, Yota Otachi

Publikováno v: Journal of Information Processing. 28:849-858

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_________::7ad9e2de7e46dd0a4797e407694f1990
https://doi.org/10.2197/ipsjjip.28.849

Zobrazit plný text záznamu

Token Sliding on Split Graphs

Autor: Eun Jung Kim, Yota Otachi, Valia Mitsou, Florian Sikora, Michael Lampis, Rémy Belmonte

Publikováno v: Theory of Computing Systems
Theory of Computing Systems, Springer Verlag, 2021, 65 (4), pp.662-686. ⟨10.1007/s00224-020-09967-8⟩
STACS 2019
STACS 2019, Mar 2019, Berlin, Germany

We consider the complexity of the Independent Set Reconfiguration problem under the Token Sliding rule. In this problem we are given two independent sets of a graph and are asked if we can transform one to the other by repeatedly exchanging a vertex

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::6b49341d15adb70eac12a1e44bef5210
https://hal.archives-ouvertes.fr/hal-03457137

Zobrazit plný text záznamu

On the complexity of finding large odd induced subgraphs and odd colorings

Autor: Rémy Belmonte, Ignasi Sau

Publikováno v: Algorithmica
Algorithmica, Springer Verlag, 2021, 83 (8), pp.2351-2373. ⟨10.1007/s00453-021-00830-x⟩
Graph-Theoretic Concepts in Computer Science 46th International Workshop, WG 2020, Leeds, UK, June 24–26, 2020, Revised Selected Papers
46th International Workshop on Graph-Theoretic Concepts in Computer Science (WG)
46th International Workshop on Graph-Theoretic Concepts in Computer Science (WG), Jun 2020, Leeds, United Kingdom. pp.67-79, ⟨10.1007/978-3-030-60440-0_6⟩
Graph-Theoretic Concepts in Computer Science ISBN: 9783030604394
WG

We study the complexity of the problems of finding, given a graph $G$, a largest induced subgraph of $G$ with all degrees odd (called an odd subgraph), and the smallest number of odd subgraphs that partition $V(G)$. We call these parameters ${\sf mos

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::cb6ec75c285563fd393535d48fa336d3
http://arxiv.org/abs/2002.06078

Zobrazit plný text záznamu

Parameterized Complexity of $$(A,\ell )$$-Path Packing

Autor: Yota Otachi, Hirotaka Ono, Yasuaki Kobayashi, Michael Lampis, Yusuke Kobayashi, Masaaki Kanzaki, Masashi Kiyomi, Tesshu Hanaka, Rémy Belmonte

Publikováno v: Lecture Notes in Computer Science ISBN: 9783030489656
IWOCA

Given a graph $G = (V,E)$, $A \subseteq V$, and integers k and $\ell $, the $(A,\ell )$ -Path Packing problem asks to find k vertex-disjoint paths of length $\ell $ that have endpoints in A and internal points in $V \setminus A$. We study

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_________::ab342f83dbc5fa5937db16a25b2da02a
https://doi.org/10.1007/978-3-030-48966-3_4

Zobrazit plný text záznamu

Parameterized Complexity of Safe Set

Autor: Michael Lampis, Ioannis Katsikarelis, Tesshu Hanaka, Rémy Belmonte, Yota Otachi, Hirotaka Ono

Publikováno v: Algorithms and Complexity, Proceedings
11th International Conference on Algorithms and Complexity (CIAC 2019)
11th International Conference on Algorithms and Complexity (CIAC 2019), May 2019, Rome, Italy. pp.38-49, ⟨10.1007/978-3-030-17402-6_4⟩
Journal of Graph Algorithms and Applications
Journal of Graph Algorithms and Applications, Brown University, 2020, 24 (3), pp.215-245. ⟨10.7155/jgaa.00528⟩
Lecture Notes in Computer Science ISBN: 9783030174019
CIAC

In this paper we study the problem of finding a small safe set S in a graph G, i.e. a non-empty set of vertices such that no connected component of G[S] is adjacent to a larger component in $G - S$. We enhance our understanding of the problem from

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::7b8497e3a41c3a66724823544eb1a251
https://hal.archives-ouvertes.fr/hal-02414438/file/1901.09434.pdf

Zobrazit plný text záznamu

Independent Set Reconfiguration Parameterized by Modular-Width

Autor: Yota Otachi, Michael Lampis, Tesshu Hanaka, Rémy Belmonte, Hirotaka Ono

Publikováno v: Graph-Theoretic Concepts in Computer Science, Revised Papers
45th International Workshop on Graph-Theoretic Concepts in Computer Science
45th International Workshop on Graph-Theoretic Concepts in Computer Science, Jun 2019, Vall de Núria, Spain. pp.285-297, ⟨10.1007/978-3-030-30786-8_22⟩
Algorithmica
Algorithmica, Springer Verlag, 2020, 82 (9), pp.2586-2605. ⟨10.1007/s00453-020-00700-y⟩
Graph-Theoretic Concepts in Computer Science ISBN: 9783030307851
WG

Independent Set Reconfiguration is one of the most well-studied problems in the setting of combinatorial reconfiguration. It is known that the problem is PSPACE-complete even for graphs of bounded bandwidth. This fact rules out the tractability of pa

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::19ab4ba3fd4bf040b550405de7740c53

Zobrazit plný text záznamu

Induced Minor Free Graphs: Isomorphism and Clique-Width

Autor: Rémy Belmonte, Yota Otachi, Pascal Schweitzer

Publikováno v: Algorithmica. 80:29-47

Given two graphs $G$ and $H$, we say that $G$ contains $H$ as an induced minor if a graph isomorphic to $H$ can be obtained from $G$ by a sequence of vertex deletions and edge contractions. We study the complexity of Graph Isomorphism on graphs that

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::a5fb2eb648869854d615b7b922321c15
https://doi.org/10.1007/s00453-016-0234-8

Zobrazit plný text záznamu

Vyhledávací nástroje:

Upřesnit hledání