Malory Marin

Malory Marin

Auto-generated profile, based on publicly available information

Malory Marin

ENS de Lyon, CNRS Université Claude Bernard Lyon 1, LIP, UMR 5668 Lyon France

Research Focus & Metrics

Academic Career Length

1Year (2026-Present)

(Calculated once Scilit publication data is synced: current year − year of first publication + 1)

Representative Publications

View All Publications
26 March 2026 in Physical Review Applied
Verified
Journal Article
Closed access
PCPierre Cazals
Pierre Cazals
AFAymeric François
Aymeric François
LHLoïc Henriet
Loïc Henriet
LLLucas Leclerc
Lucas Leclerc
MMMalory Marin
Malory Marin
CDConstantin Dalyac
Constantin Dalyac

26 October 2026 in Journal of Graph Theory
Verified
Journal Article
Open access
MMMalory Marin
Malory Marin
STStéphan Thomassé
Stéphan Thomassé
NTNicolas Trotignon
Nicolas Trotignon
RWRémi Watrigant
Rémi Watrigant
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.

3 January 2026 in Computer Networks
Verified
Journal Article
Closed access
MMMalory Marin
Malory Marin
JCJoachim Cendrier
Joachim Cendrier
LKLoïc Chassin de Kergommeaux
Loïc Chassin de Kergommeaux
RWRémi Watrigant
Rémi Watrigant
TBThomas Begin
Thomas Begin
ABAnthony Busson
Anthony Busson

8 July 2026
Verified
Thesis
Closed access
MMMalory Marin
Malory Marin
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.