Minimum clique partition in unit disk graphs

DOI10.1007/s00373-011-1026-1zbMath1244.68086arXiv0909.1552MaRDI 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 algorithm; clique partition; unit disk graph

Mathematics Subject Classification ID

05C70: Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)

05C85: Graph algorithms (graph-theoretic aspects)

05C69: Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)

68W25: Approximation algorithms

68W20: Randomized algorithms