Spanning galaxies in digraphs

Daniel Gonçalves 1 Frédéric Havet 2 Alexandre Pinlou 1 Stéphan Thomassé 1
1 ALGCO - Algorithmes, Graphes et Combinatoire
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
2 MASCOTTE - Algorithms, simulation, combinatorics and optimization for telecommunications
CRISAM - Inria Sophia Antipolis - Méditerranée , COMRED - COMmunications, Réseaux, systèmes Embarqués et Distribués
Abstract : A star is an arborescence in which the root dominates all the other vertices. A galaxy is a vertex-disjoint union of stars. The directed star arboricity of a digraph D, denoted by dst(D), is the minimum number of galaxies needed to cover A(D). In this paper, we show that dst(D)less-than-or-equals, slantΔ(D)+1 and that if D is acyclic then dst(D)less-than-or-equals, slantΔ(D). These results are proved by considering the existence of spanning galaxies in digraphs. Thus, we study the problem of deciding whether a digraph D has a spanning galaxy or not. We show that it is NP-complete (even when restricted to acyclic digraphs) but that it becomes polynomial-time solvable when restricted to strongly connected digraphs.
Type de document :
Communication dans un congrès
Jaroslav Nešetřil and André Raspaud. EuroComb: European Conference on Combinatorics, Graph Theory and Applications, Sep 2009, Bordeaux, France. Elsevier, 34, pp.139-143, 2009, Electronic Notes in Discrete Mathematics. <http://eurocomb09.labri.fr/>. <10.1016/j.endm.2009.07.023>
Liste complète des métadonnées

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00433050
Contributeur : Alexandre Pinlou <>
Soumis le : mercredi 18 novembre 2009 - 08:27:42
Dernière modification le : vendredi 9 juin 2017 - 10:42:48

Identifiants

Collections

Citation

Daniel Gonçalves, Frédéric Havet, Alexandre Pinlou, Stéphan Thomassé. Spanning galaxies in digraphs. Jaroslav Nešetřil and André Raspaud. EuroComb: European Conference on Combinatorics, Graph Theory and Applications, Sep 2009, Bordeaux, France. Elsevier, 34, pp.139-143, 2009, Electronic Notes in Discrete Mathematics. <http://eurocomb09.labri.fr/>. <10.1016/j.endm.2009.07.023>. <lirmm-00433050>

Partager

Métriques

Consultations de la notice

270