Malory Marin
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Research Subjects
Research Interests
Malory Marin has a total of 17 co-authors. Here are the top co-authors by number of shared publications:
- Rémi Watrigant
Univ Lyon, CNRS, ENS de Lyon, Université Claude Bernard Lyon 1, LIP UMR5668
3 shared publications - Anthony Busson
ENS de Lyon, CNRS, Université Claude Bernard Lyon 1, LIP, UMR 5668, Lyon, France
1 shared publication - Aymeric François
Pasqal
1 shared publication - Constantin Dalyac
Pasqal
1 shared publication - Florian Sikora
CNRS, LAMSADE, Université Paris-Dauphine, PSL University, Paris, France
1 shared publication - Joachim Cendrier
CNRS, ENS de Lyon, Inria, Université Claude Bernard Lyon 1, Lyon cedex 07, France
1 shared publication
Latest Publications
- Open Access
- 26 October 2026
- Published by Wiley in Journal of Graph Theory
A Structural Description of Zykov and Blanche Descartes Graphs
Around 1950, Zykov and Blanche Descartes proposed the two first explicit constructions of triangle‐free graphs with arbitrarily large chromatic number. We define a Zykov (resp. Blanche Descartes) graph as any induced subgraph of a graph created using Zykov's construction (resp. Blanche Descartes's). We give a structural characterization of Zykov graphs based on a specific type of stable set, that we call splitting stable set. It implies that recognizing this class is NP‐complete. We provide similar results for Blanche Descartes graphs. We also observe that any Blanche Descartes graph is a Zykov graph.
- 26 October 2026
- Published by Wiley in Journal of Graph Theory
Open AccessA Structural Description of Zykov and Blanche Descartes Graphs
Around 1950, Zykov and Blanche Descartes proposed the two first explicit constructions of triangle‐free graphs with arbitrarily large chromatic number. We define a Zykov (resp. Blanche Descartes) graph as any induced subgraph of a graph created using Zykov's construction (resp. Blanche Descartes's). We give a structural characterization of Zykov graphs based on a specific type of stable set, that we call splitting stable set. It implies that recognizing this class is NP‐complete. We provide similar results for Blanche Descartes graphs. We also observe that any Blanche Descartes graph is a Zykov graph.
- 8 July 2026
- Published by Agence Bibliographique de l'Enseignement Supérieur
Independent Sets in Graphs : Structure, Decompositions and Applications
Ensembles indépendants dans les graphes : structure, décompositions et applications: L'un des problèmes les plus fondamentaux en théorie algorithmique des graphes est le calcul d'un ensemble indépendant maximum. Ce problème est étroitement lié à la modélisation des réseaux Wi-Fi, qui peuvent être naturellement représentés comme des graphes de conflits, où les sommets correspondent aux appareils et les arêtes représentent les interférences. En raison des contraintes des protocoles, les appareils actifs simultanément doivent former un ensemble indépendant. Par conséquent, les performances (débits) des appareils dépendent de la distribution des ensembles indépendants dans le graphe. Cette observation soulève des questions algorithmiques et structurelles naturelles : quelles classes de graphes garantissent de bonnes performances, comment attribuer efficacement les canaux, et comment estimer ces mesures de performance. Nous étudions d'abord les graphes dans lesquels chaque sommet appartient à au moins un ensemble indépendant maximum, appelés graphes 1-extendable. Ces graphes garantissent un niveau minimal de performance pour tous les dispositifs. Nous examinons la complexité de la reconnaissance de tels graphes et montrons que ce problème est Theta_2^p-complet, établissant ainsi sa complexité exacte. Motivés par le problème d'attribution de canaux, nous introduisons les k-partitions 1-extendable, où l'ensemble des sommets est partitionné en k sous-graphes, chacun vérifiant cette propriété. Bien que difficile en général, nous proposons des algorithmes en temps polynomial pour certaines classes de graphes restreintes, comme celles de graphes de largeur modulaire bornée. Nous considérons ensuite une notion plus robuste fondée sur la sous-coloration, où chaque partie induit une union disjointe de cliques, garantissant une stabilité vis-à-vis des suppressions de sommets. Nous étudions ce problème dans les graphes d'intersection géométriques, qui modélisent naturellement les réseaux sans fil. Pour des classes importantes telles que les graphes de disques unitaire, nous établissons des résultats de NP-complétude ainsi que des bornes sur le nombre de couleurs. Nous concevons également et évaluons expérimentalement une heuristique simple, montrant que la sous-coloration améliore significativement l'équité dans des scénarios pratiques d'attribution de canaux.Pour estimer les performances des dispositifs, nous analysons le modèle hard-core, une distribution de probabilité sur les ensembles indépendants, ainsi que la dynamique de Glauber associée. Nous montrons que, bien que le temps de mélange soit exponentiel en général, il devient sous-exponentiel pour plusieurs classes de graphes géométriques (par exemple 2^{O(sqrt{n})} pour les graphes de disques unitaire), ce qui conduit à des algorithmes randomisés pratiques. Nous obtenons en outre des bornes quasi-polynomiales sous certaines contraintes structurelles, telles qu'un nombre d'indépendance arborescent borné, et prouvons qu'elles sont optimales. Enfin, nous étudions l'existence d'algorithmes sous-exponentiels pour la sous-coloration dans les graphes géométriques. À l'aide d'une nouvelle décomposition fondée sur des graphes ayant de petits ensembles indépendants, nous concevons un algorithme s'exécutant en temps 2^{O(n^{1 - 1/(d+1)})} pour calculer des 2-sous-colorations et établissons des bornes inférieures correspondantes. Ce résultat ne s'inscrit pas dans les cadres classiques pour les graphes d'intersection géométriques. En nous appuyant sur cette approche, nous introduisons une autre décomposition, reposant également sur des graphes à petits ensembles indépendants comme briques de base, et obtenons un algorithme robuste sous-exponentiel pour le problème du chemin hamiltonien.
- 8 July 2026
- Published by Agence Bibliographique de l'Enseignement Supérieur
Independent Sets in Graphs : Structure, Decompositions and Applications
Ensembles indépendants dans les graphes : structure, décompositions et applications: L'un des problèmes les plus fondamentaux en théorie algorithmique des graphes est le calcul d'un ensemble indépendant maximum. Ce problème est étroitement lié à la modélisation des réseaux Wi-Fi, qui peuvent être naturellement représentés comme des graphes de conflits, où les sommets correspondent aux appareils et les arêtes représentent les interférences. En raison des contraintes des protocoles, les appareils actifs simultanément doivent former un ensemble indépendant. Par conséquent, les performances (débits) des appareils dépendent de la distribution des ensembles indépendants dans le graphe. Cette observation soulève des questions algorithmiques et structurelles naturelles : quelles classes de graphes garantissent de bonnes performances, comment attribuer efficacement les canaux, et comment estimer ces mesures de performance. Nous étudions d'abord les graphes dans lesquels chaque sommet appartient à au moins un ensemble indépendant maximum, appelés graphes 1-extendable. Ces graphes garantissent un niveau minimal de performance pour tous les dispositifs. Nous examinons la complexité de la reconnaissance de tels graphes et montrons que ce problème est Theta_2^p-complet, établissant ainsi sa complexité exacte. Motivés par le problème d'attribution de canaux, nous introduisons les k-partitions 1-extendable, où l'ensemble des sommets est partitionné en k sous-graphes, chacun vérifiant cette propriété. Bien que difficile en général, nous proposons des algorithmes en temps polynomial pour certaines classes de graphes restreintes, comme celles de graphes de largeur modulaire bornée. Nous considérons ensuite une notion plus robuste fondée sur la sous-coloration, où chaque partie induit une union disjointe de cliques, garantissant une stabilité vis-à-vis des suppressions de sommets. Nous étudions ce problème dans les graphes d'intersection géométriques, qui modélisent naturellement les réseaux sans fil. Pour des classes importantes telles que les graphes de disques unitaire, nous établissons des résultats de NP-complétude ainsi que des bornes sur le nombre de couleurs. Nous concevons également et évaluons expérimentalement une heuristique simple, montrant que la sous-coloration améliore significativement l'équité dans des scénarios pratiques d'attribution de canaux.Pour estimer les performances des dispositifs, nous analysons le modèle hard-core, une distribution de probabilité sur les ensembles indépendants, ainsi que la dynamique de Glauber associée. Nous montrons que, bien que le temps de mélange soit exponentiel en général, il devient sous-exponentiel pour plusieurs classes de graphes géométriques (par exemple 2^{O(sqrt{n})} pour les graphes de disques unitaire), ce qui conduit à des algorithmes randomisés pratiques. Nous obtenons en outre des bornes quasi-polynomiales sous certaines contraintes structurelles, telles qu'un nombre d'indépendance arborescent borné, et prouvons qu'elles sont optimales. Enfin, nous étudions l'existence d'algorithmes sous-exponentiels pour la sous-coloration dans les graphes géométriques. À l'aide d'une nouvelle décomposition fondée sur des graphes ayant de petits ensembles indépendants, nous concevons un algorithme s'exécutant en temps 2^{O(n^{1 - 1/(d+1)})} pour calculer des 2-sous-colorations et établissons des bornes inférieures correspondantes. Ce résultat ne s'inscrit pas dans les cadres classiques pour les graphes d'intersection géométriques. En nous appuyant sur cette approche, nous introduisons une autre décomposition, reposant également sur des graphes à petits ensembles indépendants comme briques de base, et obtenons un algorithme robuste sous-exponentiel pour le problème du chemin hamiltonien.
- Top Cited Papers
- 26 March 2026
- Published by American Physical Society (APS) in Physical Review Applied
- Vol. 25 (3)
Identifying hard native instances for the maximum-independent-set problem on neutral-atom quantum processors
- 26 March 2026
- Published by American Physical Society (APS) in Physical Review Applied
- Vol. 25 (3)
Top Cited PapersIdentifying hard native instances for the maximum-independent-set problem on neutral-atom quantum processors
- 3 January 2026
- Published by Elsevier in Computer Networks
- Vol. 276
Fair radio channel assignment in WLANs via graph subcoloring
- 3 January 2026
- Published by Elsevier in Computer Networks
- Vol. 276
Fair radio channel assignment in WLANs via graph subcoloring