Connected Domatic Packings in Node-capacitated Graphs

Ene, Alina; Korula, Nitish J.; Vakilian, Ali

Permalink

https://hdl.handle.net/2142/48915 Copy

Description

Title

Connected Domatic Packings in Node-capacitated Graphs

Author(s)

• Ene, Alina
• Korula, Nitish J.
• Vakilian, Ali

Issue Date

2013-07

Keyword(s)

• connected dominating set
• approximation algorithms
• graph algorithms

Abstract

A set of vertices in a graph is a dominating set if every vertex outside the set has a neighbor in the set. A dominating set is connected if the subgraph induced by its vertices is connected. The connected domatic partition problem asks for a partition of the nodes into connected dominating sets. The connected domatic number of a graph is the size of a largest connected domatic partition and it is a well-studied graph parameter with applications in the design of wireless networks. In this note, we consider the fractional counterpart of the connected domatic partition problem in \emph{node-capacitated} graphs. Let $n$ be the number of nodes in the graph and let $k$ be the minimum capacity of a node separator in $G$. Fractionally we can pack at most $k$ connected dominating sets subject to the capacities on the nodes, and our algorithms construct packings whose sizes are proportional to $k$. Some of our main contributions are the following: % \begin{itemize} \item An algorithm for constructing a fractional connected domatic packing of size $\Omega\left(k \right)$ for node-capacitated planar and minor-closed families of graphs. % \item An algorithm for constructing a fractional connected domatic packing of size $\Omega\left(k / \ln{n} \right)$ for node-capacitated general graphs. % \end{itemize}

Publisher

arXiv

Type of Resource

text

Language

en

Permalink

http://hdl.handle.net/2142/48915

Owning Collections