16 citations · 97 across the 26 of their papers we have counts for
10 papers · 1 filter
Colouring the interference digraph of a set of requests in a bidirected tree
Hugo Boulier, David Coudert, Frédéric Havet +1
In this paper, we investigate the impact of the broadcast effect arising in filterless optical networks on the computational complexity of the wavelength assignment problem. We mod…
Digraph redicolouring
Nicolas Bousquet, Frédéric Havet, Nicolas Nisse +2
Given two -dicolourings of a digraph , we prove that it is PSPACE-complete to decide whether we can transform one into the other by recolouring one vertex at each step while…
Spanning eulerian subdigraphs in semicomplete digraphs
Jørgen Bang-Jensen, Frédéric Havet, Anders Yeeo
A digraph is eulerian if it is connected and every vertex has its in-degree equal to its out-degree. Having a spanning eulerian subdigraph is thus a weakening of having a hamiltoni…
On the unavoidability of oriented trees
François Dross, Frédéric Havet
A digraph is {\it -unavoidable} if it is contained in every tournament of order . We first prove that every arborescence of order with leaves is -unavoidable…
Bipartite spanning sub(di)graphs induced by 2-partitions
Jørgen Bang-Jensen, Stéphane Bessy, Frédéric Havet +1
For a given -partition of the vertices of a (di)graph , we study properties of the spanning bipartite subdigraph of induced by those arcs/edges…
Out-degree reducing partitions of digraphs
Joergen Bang-Jensen, Stéphane Bessy, Frédéric Havet +1
Let be a fixed integer. We determine the complexity of finding a -partition of the vertex set of a given digraph such that the maximum out-degree of each…