Minimum clique partition in unit disk graphs

DOI10.1007/S00373-011-1026-1MaRDI QIDQ659693zbMATH OpenOpenAlexFDO

Authors Adrian Dumitrescu, János Pach

Publication date 24 January 2012

Published in Graphs and Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/0909.1552

zbMATH Keywords

approximation algorithmclique partitionunit disk graph

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Randomized algorithms (68W20) Approximation algorithms (68W25) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Abstract: The minimum clique partition (MCP) problem is that of partitioning the vertex set of a given graph into a minimum number of cliques. Given $n$ points in the plane, the corresponding unit disk graph (UDG) has these points as vertices, and edges connecting points at distance at most~1. MCP in unit disk graphs is known to be NP-hard and several constant factor approximations are known, including a recent PTAS. We present two improved approximation algorithms for minimum clique partition in unit disk graphs: (I) A polynomial time approximation scheme (PTAS) running in time $n^{O(1/ep{s}^2)}$. This improves on a previous PTAS with $n^{O(1/ep{s}^4)}$ running time cite{PS09}. (II) A randomized quadratic-time algorithm with approximation ratio 2.16. This improves on a ratio 3 algorithm with $O(n^2)$ running time cite{CFFP04}.

Recommendations

• A Weakly Robust PTAS for Minimum Clique Partition in Unit Disk Graphs
• A weakly robust PTAS for minimum clique partition in unit disk graphs
• A note on maximum independent sets and minimum clique partitions in unit disk graphs and penny graphs: complexity and approximation
• Efficient independent set approximation in unit disk graphs
• Approximating 2-cliques in unit disk graphs

Cites work

• scientific article; zbMATH DE number 3859178 (Why is no real title available?)
• scientific article; zbMATH DE number 5764844 (Why is no real title available?)
• scientific article; zbMATH DE number 3657869 (Why is no real title available?)
• scientific article; zbMATH DE number 3209747 (Why is no real title available?)
• scientific article; zbMATH DE number 2230206 (Why is no real title available?)
• scientific article; zbMATH DE number 3056572 (Why is no real title available?)
• A Weakly Robust PTAS for Minimum Clique Partition in Unit Disk Graphs
• A still better performance guarantee for approximate graph coloring
• A weakly robust PTAS for minimum clique partition in unit disk graphs
• An Introduction to the Geometry of Numbers
• Approximation schemes for wireless networks
• Constant-Factor Approximation for Minimum-Weight (Connected) Dominating Sets in Unit Disk Graphs
• Covering convex sets with non-overlapping polygons
• Geometric clusterings
• Linear degree extractors and the inapproximability of max clique and chromatic number
• Minimum clique partition in unit disk graphs
• Polynomial-time approximation schemes for geometric graphs
• Probability and Computing
• Simple heuristics for unit disk graphs
• Unit disk graph recognition is NP-hard
• Unit disk graphs

Cited in

(17)

• scientific article; zbMATH DE number 5907542 (Why is no real title available?)
• A Weakly Robust PTAS for Minimum Clique Partition in Unit Disk Graphs
• Finding, hitting and packing cycles in subexponential time on unit disk graphs
• A weakly robust PTAS for minimum clique partition in unit disk graphs
• Good quality virtual realization of unit disk graphs
• Covering a graph with clubs
• scientific article; zbMATH DE number 7559254 (Why is no real title available?)
• Minimum bisection is NP-hard on unit disk graphs
• Approximation algorithms for intersection graphs
• Approximating 2-cliques in unit disk graphs
• Minimum clique partition in unit disk graphs
• On the chromatic number of disjointness graphs of curves
• Parameterized study of Steiner tree on unit disk graphs
• APPROXIMATION ALGORITHMS FOR A VARIANT OF DISCRETE PIERCING SET PROBLEM FOR UNIT DISKS
• On the tractability of covering a graph with 2-clubs
• scientific article; zbMATH DE number 7053376 (Why is no real title available?)
• On arrangements of orthogonal circles

This page was built for publication: Minimum clique partition in unit disk graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q659693)