Concept
Graphe de Cayley
Publications associées (81)
Complexity of mixed graph coloring
In this note we consider two coloring problems in mixed graphs, i.e., graphs containing edges and arcs. We show that they are both -complete in cubic planar bipartite graphs. This answers an open question from \cite{Ries2}. ...
2008On two coloring problems in mixed graphs
Dominique de Werra, Bernard Ries
We are interested in coloring the vertices of a mixed graph, i.e., a graph containing edges and arcs. We consider two different coloring problems: in the first one we want adjacent vertices to have different colors and the tail of an arc to get a color str ...
2008Horocyclic products of trees
Let T-1, ... , T-d be homogeneous trees with degrees q(1) + 1, ... , q(d) + 1 >= 3; respectively. For each tree, let h : Tj -> Z be the Busemann function with respect to a fixed boundary point ( end). Its level sets are the horocycles. The horocyclic produ ...
2008Loss Tomography in General Topologies with Network Coding
Network tomography infers internal network characteristics by sending and collecting probe packets from the network edge. Traditional tomographic techniques for general topologies typically use a mesh of multicast trees and/or unicast paths to cover the en ...
2007Coloring some classes of mixed graphs
We consider the coloring problem for mixed graphs, that is, for graphs containing edges and arcs. A mixed coloring is a coloring such that for every edge , and for every arc , $c(x_{p})
2007Expanding graphs, Ramanujan graphs, and 1-factor perturbations
We construct (k±1)-regular graphs which provide sequences of expanders by adding or substracting appropriate 1- factors from given sequences of k- regular graphs. We compute numerical examples in a few cases for which the given sequences are from the work ...
2006Variations of split-coloring in permutation graphs
Dominique de Werra, Tinaz Ekim
Combinatorial optimization problems related to permutations have been widely studied. Here, we consider different generalizations of the usual coloring problem in permutation graphs. A cocoloring is a partition of a permutation into increasing and decreasi ...
2006Exploring unknown environments
We consider exploration problems where a robot has to construct a complete map of an unknown environment. We assume that the environment is modeled by a directed, strongly connected graph. The robot's task is to visit all nodes and edges of the graph using ...
2000Exploring unknown environments
We consider exploration problems where a robot has to construct a complete map of an unknown environment. We assume that the environment is modeled by a directed, strongly connected graph. The robot's task is to visit all nodes and edges of the graph using ...
ACM1997Computing simulations on finite and infinite graphs
We present algorithms for computing similarity relations of labeled graphs. Similarity relations have applications for the refinement and verification of reactive systems. For finite graphs, we present an O(mn) algorithm for computing the similarity relati ...
IEEE1995