Minimum clique partition in unit disk graphs

DOI10.1007/S00373-011-1026-1zbMATH Open1244.68086arXiv0909.1552OpenAlexW1964336531MaRDI QIDQ659693FDOQ659693

János Pach, Adrian Dumitrescu

Publication date: 24 January 2012

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

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}.

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

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

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)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Unit disk graphs
• Unit disk graph recognition is NP-hard
• Title not available (Why is that?)
• Constant-Factor Approximation for Minimum-Weight (Connected) Dominating Sets in Unit Disk Graphs
• Title not available (Why is that?)
• Probability and Computing
• An Introduction to the Geometry of Numbers
• Simple heuristics for unit disk graphs
• A Weakly Robust PTAS for Minimum Clique Partition in Unit Disk Graphs
• Title not available (Why is that?)
• Approximation schemes for wireless networks
• A still better performance guarantee for approximate graph coloring
• Title not available (Why is that?)
• Minimum clique partition in unit disk graphs
• Geometric clusterings
• Covering convex sets with non-overlapping polygons
• Polynomial-time approximation schemes for geometric graphs
• A weakly robust PTAS for minimum clique partition in unit disk graphs
• Title not available (Why is that?)

Cited In (15)

• A Weakly Robust PTAS for Minimum Clique Partition in Unit Disk Graphs
• Finding, hitting and packing cycles in subexponential time on unit disk graphs
• Title not available (Why is that?)
• Minimum bisection is NP-hard on unit disk graphs
• Approximating 2-cliques in unit disk graphs
• Approximation algorithms for intersection graphs
• Minimum clique partition in unit disk graphs
• On the chromatic number of disjointness graphs of curves
• On the tractability of covering a graph with 2-clubs
• Parameterized study of Steiner tree on unit disk graphs
• APPROXIMATION ALGORITHMS FOR A VARIANT OF DISCRETE PIERCING SET PROBLEM FOR UNIT DISKS
• Title not available (Why is that?)
• On arrangements of orthogonal circles
• Covering a Graph with Clubs
• Title not available (Why is that?)

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)