The spanning galaxy problem

Daniel Gonçalves 1 Frédéric Havet 2 Alexandre Pinlou 1 Stéphan Thomassé 3
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 : 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.
Type de document :
Article dans une revue
Discrete Applied Mathematics, Elsevier, 2012, 160 (6), pp.744-754
Liste complète des métadonnées

Littérature citée [11 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-00749191
Contributeur : Frederic Havet <>
Soumis le : dimanche 23 octobre 2016 - 16:04:19
Dernière modification le : lundi 4 décembre 2017 - 15:14:09

Fichier

pagro-revised.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-00749191, version 1

Citation

Daniel Gonçalves, Frédéric Havet, Alexandre Pinlou, Stéphan Thomassé. The spanning galaxy problem. Discrete Applied Mathematics, Elsevier, 2012, 160 (6), pp.744-754. 〈hal-00749191〉

Partager

Métriques

Consultations de la notice

356

Téléchargements de fichiers

86