17 citations · 31 across the 6 of their papers we have counts for
8 papers
Trade-off between Time, Space, and Workload: the case of the Self-stabilizing Unison
Stéphane Devismes, David Ilcinkas, Colette Johnen +1
We present a self-stabilizing algorithm for the (asynchronous) unison problem which achieves an efficient trade-off between time, workload, and space in a weak model. Precisely, ou…
Distributed Certification for Classes of Dense Graphs
Pierre Fraigniaud, Frédéric Mazoit, Pedro Montealegre +2
A proof-labeling scheme (PLS) for a boolean predicate on labeled graphs is a mechanism used for certifying the legality with respect to of global network states in a distri…
Making local algorithms efficiently self-stabilizing in arbitrary asynchronous environments
Stéphane Devismes, David Ilcinkas, Colette Johnen +1
This paper deals with the trade-off between time, workload, and versatility in self-stabilization, a general and lightweight fault-tolerant concept in distributed computing.In this…
A single exponential bound for the redundant vertex Theorem on surfaces
Frédéric Mazoit
Let s1, t1,. . . sk, tk be vertices in a graph G embedded on a surface σof genus g. A vertex v of G is "redundant" if there exist k vertex disjoint paths linking si and ti (1 \lequ…
A simple proof of the tree-width duality theorem
Frédéric Mazoit
We give a simple proof of the "tree-width duality theorem" of Seymour and Thomas that the tree-width of a finite graph is exactly one less than the largest order of its brambles.
Tree-width of hypergraphs and surface duality
Frédéric Mazoit
In Graph Minors III, Robertson and Seymour write: "It seems that the tree-width of a planar graph and the tree-width of its geometric dual are approximately equal - indeed, we have…
Partitions versus sets : a case of duality
Laurent Lyaudet, Frédéric Mazoit, Stephan Thomasse
In a recent paper, Amini et al. introduce a general framework to prove duality theorems between special decompositions and their dual combinatorial object. They thus unify all know…
Tree-width of hypergraphs and surface duality
Frédéric Mazoit
In Graph Minor III, Robertson and Seymour conjecture that the tree-width of a planar graph and that of its dual differ by at most one. We prove that given a hypergraph H on a surfa…