1 citations · 1 across the 7 of their papers we have counts for
8 papers
Small Independent Sets versus Small Separator in Geometric Intersection Graphs
Malory Marin, Rémi Watrigant
While most classical NP-hard graph problems cannot be solved in time on general graphs under the Exponential Time Hypothesis (ETH), many exhibit the square-root phenomen…
Robust Algorithms for Path and Cycle Problems in Geometric Intersection Graphs
Malory Marin, Jean-Florent Raymond, Rémi Watrigant
We study the design of robust subexponential algorithms for classical connectivity problems on intersection graphs of similarly sized fat objects in . In this setting…
Subexponential and Parameterized Mixing Times of Glauber Dynamics on Independent Sets
Malory Marin
Given a graph , the hard-core model defines a probability distribution over its independent sets, assigning to each set of size a probability of , where …
Identifying hard native instances for the maximum independent set problem on neutral atoms quantum processors
Pierre Cazals, Aymeric François, Loïc Henriet +9
The Maximum Independent Set (MIS) problem is a fundamental combinatorial optimization task that can be naturally mapped onto the Ising Hamiltonian of neutral atom quantum processor…
A structural description of Zykov and Blanche Descartes graphs
Malory Marin, Stéphan Thomassé, Nicolas Trotignon +1
In 1949, Zykov proposed the first explicit construction of triangle-free graphs with arbitrarily large chromatic number. We define a Zykov graph as any induced subgraph of a graph…
Channel allocation revisited through 1-extendability of graphs
Anthony Busson, Malory Marin, Rémi Watrigant
We revisit the classical problem of channel allocation for Wi-Fi access points (AP). Using mechanisms such as the CSMA/CA protocol, Wi-Fi access points which are in conflict within…
Beyond recognizing well-covered graphs
Carl Feghali, Malory Marin, Rémi Watrigant
We prove a number of results related to the computational complexity of recognizing well-covered graphs. Let and be positive integers and let be a graph. Then is sa…
Three remarks on graphs
Carl Feghali, Malory Marin
Let . A graph is if for any pairwise disjoint independent vertex subsets in , there exist pairwise disjoint maximum indepe…