## Files in this item

Files | Description | Format |
---|---|---|

application/pdf domatic-packing.pdf (162kB) | (no description provided) |

## Description

Title: | Connected Domatic Packings in Node-capacitated Graphs |

Author(s): | Ene, Alina; Korula, Nitish J.; Vakilian, Ali |

Subject(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} |

Issue Date: | 2013-07 |

Publisher: | arXiv |

Genre: | Article |

Type: | Text |

Language: | English |

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

Publication Status: | published or submitted for publication |

Peer Reviewed: | not peer reviewed |

Date Available in IDEALS: | 2014-04-22 |