The Algorithmic Complexity of k-Domatic Partition of GraphsReportar como inadecuado

The Algorithmic Complexity of k-Domatic Partition of Graphs - Descarga este documento en PDF. Documentación en PDF para descargar gratis. Disponible también para leer online.

1 Tsinghua University Beijing

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}+o1\ln n$, generalizing the 1 + o1ln 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.

Autor: Hongyu Liang -



Documentos relacionados