Author name cluster

Stéphane Rovedakis

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

2 papers

1 author row

TCS Journal 2024 Journal Article

On the complexity of Dominating Set for graphs with fixed diameter

Valentin Bouquet
François Delbot
Christophe Picouleau
Stéphane Rovedakis

A set S ⊆ V of a graph G = ( V, E ) is a dominating set if each vertex has a neighbor in S or belongs to S. Dominating Set is the problem of deciding, given a graph G and an integer k ≥ 1, if G has a dominating set of size at most k. It is well known that this problem is NP -complete even for claw-free graphs. We give a (almost) complexity dichotomy for Dominating Set for the class of claw-free graphs with diameter d. We show that the problem is NP -complete for every fixed d ≥ 3 and polynomial-time solvable for d ≤ 2. To prove the case d = 2, we show that Minimum Maximal Matching can be solved in polynomial-time for 2 K 2 -free graphs.

Details DOI

I&C Journal 2019 Journal Article

The first fully polynomial stabilizing algorithm for BFS tree construction

Alain Cournier
Stéphane Rovedakis
Vincent Villain

The construction of a spanning tree is a fundamental task in distributed systems which allows to resolve other tasks (i. e. , routing, mutual exclusion, network reset). In this paper, we are interested in the problem of constructing a Breadth First Search (BFS) tree. Stabilization is a versatile technique which ensures that the system recovers a correct behavior from an arbitrary global state resulting from transient faults. A fully polynomial algorithm has a round complexity in O ( d a ) and a step complexity in O ( n b ) where d and n are the diameter and the number of nodes of the network and a and b are constants. We present the first fully polynomial stabilizing algorithm constructing a BFS tree under a distributed daemon. Moreover, as far as we know, it is also the first fully polynomial stabilizing algorithm for spanning tree construction. Its round complexity is in Θ ( d 2 ) and its step complexity is in O ( n 6 ).

Details DOI