A PTAS for Minimum Clique Partition in Unit Disk Graphs Open Access
Descriptions
 Author or creator

Pirwani, Imran
Salavatipour, Mohammad
 Additional contributors

 Subject/Keyword

Distributed computation
Polynomial time approximation scheme
Unit disk graphs
Clique partition
 Type of item
 Computing Science Technical Report
 Computing science technical report ID

TR0906
 Language

English
 Place
 Time
 Description

Technical report TR0906. We consider the problem of partitioning the set of vertices of a given unit disk graph (UDG) into a minimum number of cliques. The problem is NPhard and various constant factor approximations are known, with the current best ratio of 3. Our main result is a polynomial time approximation scheme (PTAS) for this problem on UDG. In fact, we present a robust algorithm that given a graph G (not necessarily UDG) with edgelengths, it either (i) computes a clique partition or (ii) gives a certificate that the graph is not a UDG; for the case (i) that it computes a clique partition, we show that it is guaranteed to be within (1 + ε) ratio of the optimum if the input is UDG; however if the input is not a UDG it either computes a clique partition as in case (i) with no guarantee on the quality of the clique partition or detects that it is not a UDG. Noting that recognition of UDG's is NPhard even if we are given edge lengths, our PTAS is a robust algorithm. Our algorithm can be transformed into an O (log*n/εο(1))time distributed polynomialtime approximation scheme (PTAS). Finally, we consider a weighted version of the clique partition problem on vertex weighted UDGs; the weight of a clique is the weight of a heaviest vertex in it, and the weight of a clique partition is the sum of the weights of the cliques in it. This formulation generalizes the classical clique partition problem. We show that the problem admits a (2 + ε)approximation algorithm for the weighted version of the problem where the graph is expressed in standard form, for example, as an adjacency matrix. This improves on the best known algorithm which constructs an 8approximation for the unweighted case for UDGs expressed in standard form.
 Date created

2009
 DOI

doi:10.7939/R3W37KX2Q
 License information
 Creative Commons Attribution 3.0 Unported
 Rights
 Citation for previous publication

 Source
 Link to related item

File Details
 Date Uploaded
 20120605T16:02:16.000Z
 Date Modified
 20140424T23:36:36.263+00:00
 Audit Status
 Audits have not yet been run on this file.
 Characterization

File format: pdf (Portable Document Format)
Mime type: application/pdf
File size: 343453
Last modified: 2015:10:12 16:56:2906:00
Filename: TR0906.pdf
Original checksum: 1db159f6751d689dbf11a1f7e1a1409c
Well formed: true
Valid: true
Page count: 27
Activity of users you follow
User Activity 
Date 