Files in this item

FilesDescriptionFormat

application/pdf

application/pdfdomatic-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


This item appears in the following Collection(s)

Item Statistics