The Algorithmic Complexity of k-Domatic Partition of Graphs

Abstract : Let G = (V,E) be a simple undirected graph, and k be a positive integer. A k-dominating set of G is a set of vertices S ⊆ V satisfying that every vertex in V ∖ S is adjacent to at least k vertices in S. A k-domatic partition of G is a partition of V into k-dominating sets. The k-domatic number of G is the maximum number of k-dominating sets contained in a k-domatic partition of G. In this paper we study the k-domatic number from both algorithmic complexity and graph theoretic points of view. We prove that it is $\mathcal{NP}$-complete to decide whether the k-domatic number of a bipartite graph is at least 3, and present a polynomial time algorithm that approximates the k-domatic number of a graph of order n within a factor of $(\frac{1}{k}+o(1))\ln n$, generalizing the (1 + o(1))ln n approximation for the 1-domatic number given in [5]. In addition, we determine the exact values of the k-domatic number of some particular classes of graphs.
Type de document :
Communication dans un congrès
Jos C. M. Baeten; Tom Ball; Frank S. Boer. 7th International Conference on Theoretical Computer Science (TCS), Sep 2012, Amsterdam, Netherlands. Springer, Lecture Notes in Computer Science, LNCS-7604, pp.240-249, 2012, Theoretical Computer Science. 〈10.1007/978-3-642-33475-7_17〉
Liste complète des métadonnées

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

https://hal.inria.fr/hal-01556216
Contributeur : Hal Ifip <>
Soumis le : mardi 4 juillet 2017 - 17:45:40
Dernière modification le : mardi 4 juillet 2017 - 17:47:02
Document(s) archivé(s) le : vendredi 15 décembre 2017 - 02:37:44

Fichier

978-3-642-33475-7_17_Chapter.p...
Fichiers produits par l'(les) auteur(s)

Licence


Distributed under a Creative Commons Paternité 4.0 International License

Identifiants

Citation

Hongyu Liang. The Algorithmic Complexity of k-Domatic Partition of Graphs. Jos C. M. Baeten; Tom Ball; Frank S. Boer. 7th International Conference on Theoretical Computer Science (TCS), Sep 2012, Amsterdam, Netherlands. Springer, Lecture Notes in Computer Science, LNCS-7604, pp.240-249, 2012, Theoretical Computer Science. 〈10.1007/978-3-642-33475-7_17〉. 〈hal-01556216〉

Partager

Métriques

Consultations de la notice

37

Téléchargements de fichiers

31