Personne
Dominique de Werra
Publications associées (46)
Graph Transformations preserving the stability number
We analyze the relations between several graph transformations that were introduced to be used in procedures determining the stability number of a graph. We show that all these transformations can be decomposed into a sequence of edge deletions and twin de ...
Elsevier Science Bv2012d-Transversals of stable sets and vertex covers in weighted bipartite graphs
Dominique de Werra, Bernard Ries
Let G=(V,E)G=(V,E) be a graph in which every vertex v∈Vv∈V has a weight w(v)⩾0w(v)⩾0 and a cost c(v)⩾0c(v)⩾0. Let SGSG be the family of all maximum-weight stable sets in G . For any integer d⩾0d⩾0, a minimum d-transversal in the graph G with respect to SGS ...
2012Minimum d-blockers and d-transversals in graphs
We consider a set V of elements and an optimization problem on V: the search for a maximum (or minimum) cardinality subset of V verifying a given property a"similar to. A d-transversal is a subset of V which intersects any optimum solution in at least d el ...
2011Split-critical and uniquely split-colorable graphs
Dominique de Werra, Bernard Ries, Tinaz Ekim
The split-coloring problem is a generalized vertex coloring problem where we partition the vertices into a minimum number of split graphs. In this paper, we study some notions which are extensively studied for the usual vertex coloring and the cocoloring p ...
2010A projective algorithm for preemptive open shop scheduling with two multiprocessor groups
We study a multiprocessor extension of the preemptive open shop scheduling problem, where the set of processors is partitioned into processor groups. We show that the makespan minimization problem is polynomially solvable for two multiprocessor groups even ...
2010On the use of graphs in discrete tomography
Dominique de Werra, Bernard Ries
In this tutorial paper, we consider the basic image reconstruction problem which stems from discrete tomography. We derive a graph theoretical model and we explore some variations and extensions of this model. This allows us to establish connections with s ...
2010Blockers and transversals in some subclasses of bipartite graphs: When caterpillars are dancing on a grid
Dominique de Werra, Bernard Ries
Given an undirected graph G = (V, E) with matching number nu(G), a d-blocker is a subset of edges B such that nu((V, E \ B))
2010A tutorial on the use of graph coloring for some problems in robotics
Dominique de Werra, Tinaz Ekim
We study the problem where a robot has to pick up items of different sizes which are stored along a corridor. A natural requirement is that the items have to be collected in decreasing order of their sizes. We deal with various systems according to the loc ...
2009Graph coloring with cardinality constraints on the neighborhoods
Dominique de Werra, Bernard Ries
Extensions and variations of the basic problem of graph coloring are introduced. The problem consists essentially in finding in a graph G a k-coloring, i.e., a partition V-1,...,V-k of the vertex set of G such that, for some specified neighborhood (N) over ...
2009Degree-constrained edge partitioning in graphs arising from discrete tomography
Dominique de Werra, Bernard Ries
Starting from the basic problem of reconstructing a 2-dimensional image given by its projections on two axes, one associates a model of edge coloring in a complete bipartite graph. The complexity of the case with k=3 colors is open. Variations and special ...
2009