A weakly robust PTAS for minimum clique partition in unit disk graphs
From MaRDI portal
Publication:2428685
DOI10.1007/s00453-011-9503-8zbMath1236.68299arXiv0904.2203OpenAlexW2156300926MaRDI QIDQ2428685
Imran A. Pirwani, Mohammad R. Salavatipour
Publication date: 26 April 2012
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/0904.2203
Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Approximation algorithms (68W25)
Related Items
A weakly robust PTAS for minimum clique partition in unit disk graphs ⋮ Covering a Graph with Clubs ⋮ Minimum clique partition in unit disk graphs ⋮ An optimal maximal independent set algorithm for bounded-independence graphs ⋮ On the tractability of covering a graph with 2-clubs
Cites Work
- Unnamed Item
- Unnamed Item
- Partition into cliques for cubic graphs: Planar case, complexity and approximation
- A weakly robust PTAS for minimum clique partition in unit disk graphs
- Batch processing with interval graph compatibilities between tasks
- A log-star distributed maximal independent set algorithm for growth-bounded graphs
- Clique partitioning of interval graphs with submodular costs on the cliques
- Geometric clusterings
- Good Quality Virtual Realization of Unit Ball Graphs
- A Weakly Robust PTAS for Minimum Clique Partition in Unit Disk Graphs
- Approximation Algorithms for Domatic Partitions of Unit Disk Graphs
- Approximation schemes for covering and packing problems in image processing and VLSI
- Robust algorithms for restricted domains
- Distributed Computing: A Locality-Sensitive Approach
- Approximation schemes for wireless networks
- On the complexity of distributed graph coloring
- Algorithmic Aspects of Wireless Sensor Networks
- Distributed Computing
- Latency Constrained Aggregation in Sensor Networks
