A Weakly Robust PTAS for Minimum Clique Partition in Unit Disk Graphs
From MaRDI portal
Publication:3569890
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
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
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