On Spanning Galaxies in Digraphs - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Article Dans Une Revue Discrete Applied Mathematics Année : 2012

On Spanning Galaxies in Digraphs

Résumé

In a directed graph, a star is an arborescence with at least one arc, in which the root dominates all the other vertices. A galaxy is a vertex-disjoint union of stars. In this paper, we consider the Spanning Galaxy problem of deciding whether a digraph D has a spanning galaxy or not. We show that although this problem is NP-complete (even when restricted to acyclic digraphs), it becomes polynomial-time solvable when restricted to strong digraphs. In fact, we prove that restricted to this class, the \pb\ is equivalent to the problem of deciding if a strong digraph has a strong digraph with an even number of vertices. We then show a polynomial-time algorithm to solve this problem. We also consider some parameterized version of the Spanning Galaxy problem. Finally, we improve some results concerning the notion of directed star arboricity of a digraph D, which is the minimum number of galaxies needed to cover all the arcs of D. We show in particular that dst(D)\leq \Delta(D)+1 for every digraph D and that dst(D)\leq \Delta(D) for every acyclic digraph D.
Fichier principal
Vignette du fichier
pagro-revised.pdf (208.06 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-00749191 , version 1 (23-10-2016)

Identifiants

Citer

Daniel Gonçalves, Frédéric Havet, Alexandre Pinlou, Stéphan Thomassé. On Spanning Galaxies in Digraphs. Discrete Applied Mathematics, 2012, 160 (6), pp.744-754. ⟨10.1016/j.dam.2011.07.013⟩. ⟨hal-00749191⟩
362 Consultations
99 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More