Minimum clique partition in unit disk graphs

DOI10.1007/s00373-011-1026-1zbMath1244.68086arXiv0909.1552OpenAlexW1964336531MaRDI QIDQ659693

János Pach, Adrian Dumitrescu

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

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

Related Items (11)

APPROXIMATION ALGORITHMS FOR A VARIANT OF DISCRETE PIERCING SET PROBLEM FOR UNIT DISKS ⋮ On arrangements of orthogonal circles ⋮ Parameterized study of Steiner tree on unit disk graphs ⋮ Covering a Graph with Clubs ⋮ Approximation algorithms for intersection graphs ⋮ Minimum clique partition in unit disk graphs ⋮ Unnamed Item ⋮ On the tractability of covering a graph with 2-clubs ⋮ On the chromatic number of disjointness graphs of curves ⋮ Finding, hitting and packing cycles in subexponential time on unit disk graphs ⋮ Unnamed Item

Cites Work

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

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