Speaker: Dr. Mohammad R. Salavatipour
Assistant Professor
Department of Computing Science
University of Alberta, Canada
Title: Partitioning Nodes of a Wireless Network into a Small Number of Cliques
Local Host: Mohsen Taghaddosi
Time: Tuesday, December 30th, 2008, 12:45am-1:30 pm
Kharazmi Hall, Department of Computer Engineering
Sharif University of Technology, Tehran
We consider the problem of partitioning the set of vertices of a given unit disk graph (UDG) into a minimum number of cliques. One of the most commonly used network model for homogeneous networks is the unit disk graph, therefore many problems on such networks are modeled using problems on UDGs. Among others, good clique partition on such graphs permits guaranteed geographic routing on a related class of graphs. The clique partition problem on UDGs is NP-hard and various constant factor approximations are known, with the current best ratio of . The main result of this talk is a polynomial time approximation scheme (PTAS) for this problem on UDG. In fact, we present a more general algorithm that given a (not necessarily UDG) graph G with edge lengths, either computes a clique partition or gives a certificate that the graph is not a UDG; for the case that it computes a clique partition, we show that it is guaranteed to be within $(1+\eps)$ ratio of the optimum if the input is UDG. Noting that recognition of UDG’s is NP-hard (even if we are given edge lengths), our PTAS is a robust algorithm. Also, by modifying existing algorithms, we show that if we are given a DG with its geometric realization on the plane (i.e. location of points) then
we can compute, in randomized quadratic time a $2.16$ approximate clique partition.
