Files in this item

FilesDescriptionFormat

application/pdf

domatic-packing.pdf (162kB)
(no description provided)PDF

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
﻿