Bouquet, Valentin Delbot, François Picouleau, Christophe

We characterize the vertices belonging to all minimum dominating sets, to some minimum dominating sets but not all, and to no minimum dominating set. We refine this characterization for some well studied sub-classes of graphs: chordal, claw-free, triangle-free. Also we exhibit some graphs answering to some open questions of the literature on minimu...

Bensmail, Julien Das, Sandip Nandi, Soumen Pierron, Théo Paul, Soumyajit Sen, Sagnik Sopena, Eric

Pushable homomorphisms and the pushable chromatic number $\chi_p$ of oriented graphs were introduced by Klostermeyer and MacGillivray in 2004. They notably observed that, for any oriented graph $\overrightarrow{G}$, we have $\chi_p(\overrightarrow{G}) \leq \chi_o(\overrightarrow{G}) \leq 2 \chi_p(\overrightarrow{G})$, where $\chi_o(\overrightarrow{...

Bensmail, Julien Li, Bi Li, Binlong Nisse, Nicolas

The 1-2-3 Conjecture asserts that, for every connected graph different from K2 , its edges can be labeled with 1,2,3 so that, when coloring each vertex with the sum of its incident labels, no two adjacent vertices get the same color. This conjecture takes place in the more general context of distinguishing labelings, where the goal is to label grap...

Falk, Martin Garth, Christoph Gueunet, Charles Guillou, Pierre Gyulassy, Attila Hofmann, Lutz Kappe, Christopher Levine, Joshua Lukasczyk, Jonas Tierny, Julien
...

This tutorial presents topological methods for the analysis and visualization of scientific data from a user’s perspective, with the Topology ToolKit (TTK), an open-source library for topological data analysis. Topological methods have gained considerably in popularity and maturity over the last twenty years and success stories of established metho...

Doraiswamy, Harish Tierny, Julien Silva, Paulo Nonato, Gustavo Silva, Claudio

Multidimensional Projection is a fundamental tool for high-dimensional data analytics and visualization. With very few exceptions, projection techniques are designed to map data from a high-dimensional space to a visual space so as to preserve some dissimilarity (similarity) measure, such as the Euclidean distance for example. In fact, although ado...

Lukasczyk, Jonas Garth, Christoph Maciejewski, Ross Tierny, Julien

This paper describes a localized algorithm for the topological simplification of scalar data, an essential pre-processing step of topological data analysis (TDA). Given a scalar field f and a selection of extrema to preserve, the proposed localized topological simplification (LTS) derives a function g that is close to f and only exhibits the select...

Rioul, Olivier

A framework for deriving Rényi entropy-power inequalities (REPIs) is presented that uses linearization and an inequality of Dembo, Cover, and Thomas. Simple arguments are given to recover the previously known Rényi EPIs and derive new ones, by unifying a multiplicative form with constant c and a modification with exponent α of previous works. An in...

Dujmović, Vida Esperet, Louis Morin, Pat Walczak, Bartosz Wood, David R.

A (not necessarily proper) vertex colouring of a graph has "clustering" $c$ if every monochromatic component has at most $c$ vertices. We prove that planar graphs with maximum degree $\Delta$ are 3-colourable with clustering $O(\Delta^2)$. The previous best bound was $O(\Delta^{37})$. This result for planar graphs generalises to graphs that can be ...

Pépin, Martin Genitrini, Antoine Peschanski, Frédéric

We study the combinatorial structure of the state-space of non-deterministic fork-join processes. As a first step we establish a link between concurrent programs and a class of combinatorial structures based on the notion of increasing labelling. Beyond the theory, our goal is to develop algorithms and tools for the statistical analysis of the proc...

Gastineau, Nicolas Abdou, Wahabou Mbarek, Nader Togni, Olivier

In this paper, we present two deterministic leader election algorithms for programmable matter on the face-centered cubic grid. The face-centered cubic grid is a 3-dimensional 12-regular infinite grid that represents an optimal way to pack spheres (i.e., spherical particles or modules in the context of the programmable matter) in the 3-dimensional ...