Pilavci, Yusuf Amblard, Pierre-Olivier Barthelme, Simon Tremblay, Nicolas

Another facet of the elegant link between random processes on graphs and Laplacian-based numerical linear algebra is uncovered: based on random spanning forests, novel Monte-Carlo estimators for graph signal smoothing are proposed. These random forests are sampled efficiently via a variant of Wilson's algorithm-in time linear in the number of edges...

Bentz, Cédric Le Bodic, Pierre

International audience

Liu, Jin-Yi

Given two positive integers n and k with k ≤ n, let X denote the family of all the k-subsets of [n] := {1, 2, ..., n}. In this paper, assuming that the k-subsets in X hold some order of ranks, we consider the expected number of left-to-right maxima in some sequential ordering of X , under a random permutation of [n]. In the case k = 1, it is well-k...

Bonfante, Guillaume Couceiro, Miguel

The termination issue we tackle is rooted in natural language processing where graph rewriting systems (GRS) may contain a large number of rules, often in the order of thousands. Decidable concepts thus become mandatory to verify the termination of such systems. The notion of graph rewriting consider does not make any assumption on the structure of...

Bouquet, Valentin Picouleau, Christophe

We prove that the Minimum Dominating Set problem is polynomial for the class of (claw, P8)-free graphs.

Portase, Raluca Uçar, Bora

International audience

cousin, xavier

This paper contributes to the conclusion that P=NP by the description of an algorithm with a polynomial complexity for the chromatic index research of any bridgeless cubic graph (3-regular). Ian Holyer [2] showed that all resolution of a 3-SAT problem is deduced from the research of index chromatic in cubic graph which by construction is bridgeless...

Bonamy, Marthe Pilipczuk, Michał Sereni, Jean-Sébastien

We consider a classic rendezvous game where two players try to meet each other on a set of n locations. In each round, every player visits one of the locations and the game finishes when the players meet at the same location. The goal is to devise strategies for both players that minimize the expected waiting time till the rendezvous. In the asymme...

Nguyen, Thanh Tuan Nguyen, Thanh Phuong Bouchara, Frédéric

A novel effective operator, named HIerarchical LOcal Pattern (HILOP), is proposed to efficiently exploit relationships of local neighbors at each adjacent pairwise of different regional hierarchies located surrounding a center pixel of a texture image. Instead of thresh-olding by the value of central pixel, the gray-scale of each local neighbor in ...

Fimmel, Elena Michel, Christian Pirot, François Sereni, Jean-Sébastien Starman, Martin Strüngmann, Lutz

A code X is k-circular if any concatenation of at most k words from X, when read on a circle, admits exactly one partition into words from X. It is circular if it is k-circular for every integer k. While it is not a priori clear from the definition, there exists, for every pair (n,ℓ), an integer k such that every k-circular ℓ-letter code over an al...