22 citations
Counting papers with at most 25 authors, so collaboration author lists do not stand in for the people here.
- Centre National de la Recherche ScientifiqueFR7 papers
- Institut national de recherche en sciences et technologies du numériqueFR6 papers
- Laboratoire d'Informatique, Signaux et Systèmes de Sophia AntipolisFR6 papers
- Université Côte d'AzurFR5 papers
- Laboratoire Bordelais de Recherche en InformatiqueFR3 papers
- École Normale Supérieure de LyonFR2 papers
- McGill UniversityCA2 papers
- University of Rome Tor VergataIT2 papers
- AGH University of KrakowPL1 paper
- Aix-Marseille UniversitéFR1 paper
- Center for Mathematical ModelingCL1 paper
- Columbia UniversityUS1 paper
15 papers
Planning with Biological Neurons and Synapses
Francesco d'Amore, Daniel Mitropolsky, Pierluigi Crescenzi +2
We revisit the planning problem in the blocks world, and we implement a known heuristic for this task. Importantly, our implementation is biologically plausible, in the sense that…
Hyperbolicity Computation through Dominating Sets
David Coudert, André Nusser, Laurent Viennot
Hyperbolicity is a graph parameter related to how much a graph resembles a tree with respect to distances. Its computation is challenging as the main approaches consist in scanning…
Generalising the achromatic number to Zaslavsky's colourings of signed graphs
Julien Bensmail, François Dross, Nacim Oijid +1
The chromatic number, which refers to the minimum number of colours required to colour the vertices of graphs properly, is one of the most central notions of the graph chromatic th…
A proof of the Multiplicative 1-2-3 Conjecture
Julien Bensmail, Hervé Hocquard, Dimitri Lajou +1
We prove that the product version of the 1-2-3 Conjecture, raised by Skowronek-Kazi{ó}w in 2012, is true. Namely, for every connected graph with order at least 3, we prove that we…
Modularity of minor-free graphs
Michał Lasoń, Małgorzata Sulkowska
We prove that a class of graphs with an excluded minor and with the maximum degree sublinear in the number of edges is maximally modular, that is, modularity tends to 1 as the numb…
Phase Transition of a Non-Linear Opinion Dynamics with Noisy Interactions
Francesco d'Amore, Andrea Clementi, Emanuele Natale
In several real \emph{Multi-Agent Systems} (MAS), it has been observed that only weaker forms of\emph{metastable consensus} are achieved, in which a large majority of agents agree…
Search via Parallel Lévy Walks on
Andrea Clementi, Francesco d'Amore, George Giakkoupis +1
Motivated by the Lévy foraging hypothesis -- the premise that various animal species have adapted to follow Lévy walks to optimize their search efficiency -- we study the parallel…
NP-completeness of the game Kingdomino
Viet-Ha Nguyen, Kevin Perrot, Mathieu Vallet
Kingdomino is a board game designed by Bruno Cathala and edited by Blue Orange since 2016. The goal is to place dominoes on a grid layout, and get a better score than…
Computing metric hulls in graphs
Kolja Knauer, Nicolas Nisse
We prove that, given a closure function the smallest preimage of a closed set can be calculated in polynomial time in the number of closed sets. This confirms a conjecture of Alben…
On a combination of the 1-2-3 Conjecture and the Antimagic Labelling Conjecture
Julien Bensmail, Mohammed Senhaji, Kasper Szabo Lyngsie
This paper is dedicated to studying the following question: Is it always possible to injectively assign the weights to the edges of any given graph (with no comp…
A Variant of the Erdős-Sós Conjecture
Frédéric Havet, Bruce Reed, Maya Stein +1
A well-known conjecture of Erdős and Sós states that every graph with average degree exceeding contains every tree with edges as a subgraph. We propose a variant of this…
On computing tree and path decompositions with metric constraints on the bags
Guillaume Ducoffe, Sylvain Legay, Nicolas Nisse
We here investigate on the complexity of computing the \emph{tree-length} and the \emph{tree-breadth} of any graph , that are respectively the best possible upper-bounds on the…
How to determine if a random graph with a fixed degree sequence has a giant component
Felix Joos, Guillem Perarnau, Dieter Rautenbach +1
For a fixed degree sequence , let be a uniformly chosen (simple) graph on where the vertex has degree . In this p…
Colouring graphs with constraints on connectivity
Pierre Aboulker, Nick Brettell, Frédéric Havet +2
A graph has maximal local edge-connectivity if the maximum number of edge-disjoint paths between every pair of distinct vertices and is at most . We prove Brooks…
List Colouring Squares of Planar Graphs
Frédéric Havet, Jan van den Heuvel, Colin McDiarmid +1
In 1977, Wegner conjectured that the chromatic number of the square of every planar graph with maximum degree is at most . We show t…