A Weakly Robust PTAS for Minimum Clique Partition in Unit Disk Graphs
DOI10.1007/978-3-642-13731-0_19zbMATH Open1284.05220OpenAlexW2571163292MaRDI QIDQ3569890FDOQ3569890
Authors: Imran A. Pirwani, Mohammad 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
Recommendations
- A weakly robust PTAS for minimum clique partition in unit disk graphs
- Approximation and Online Algorithms
- Graph-Theoretic Concepts in Computer Science
- Minimum clique partition in unit disk graphs
- A PTAS for weak minimum routing cost connected dominating set of unit disk graph
- Approximation algorithms for finding and partitioning unit-disk graphs into co-\(k\)-plexes
- PTAS for the minimum \(k\)-path connected vertex cover problem in unit disk graphs
- QPTAS and subexponential algorithm for maximum clique on disk graphs
- EPTAS and Subexponential Algorithm for Maximum Clique on Disk and Unit Ball Graphs
- Ruling Out PTAS for Graph Min‐Bisection, Dense k‐Subgraph, and Bipartite Clique
Graph algorithms (graph-theoretic aspects) (05C85) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) 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)
Cited In (6)
- 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
- Approximation and Online Algorithms
This page was built for publication: A Weakly Robust PTAS for 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 Q3569890)
