A Weakly Robust PTAS for Minimum Clique Partition in Unit Disk Graphs

DOI10.1007/978-3-642-13731-0_19zbMath1284.05220OpenAlexW2571163292MaRDI QIDQ3569890

Imran A. Pirwani, Mohammad R. Salavatipour

Publication date: 22 June 2010

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-13731-0_19

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Approximation algorithms (68W25)

Related Items (5)

A weakly robust PTAS for minimum clique partition in unit disk graphs ⋮ Shifting strategy for geometric graphs without geometry ⋮ Approximation algorithms for intersection graphs ⋮ 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

This page was built for publication: A Weakly Robust PTAS for Minimum Clique Partition in Unit Disk Graphs