A Weakly Robust PTAS for Minimum Clique Partition in Unit Disk Graphs
From MaRDI portal
Publication:3569890
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)
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
Cited in
(6)- Minimum clique partition in unit disk graphs
- A weakly robust PTAS for 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
- Shifting strategy for geometric graphs without geometry
- Approximation algorithms for intersection graphs
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)
