Minimum clique partition in unit disk graphs (Q659693): Difference between revisions
From MaRDI portal
Added link to MaRDI item. |
Changed an Item |
||
(4 intermediate revisions by 3 users not shown) | |||
Property / reviewed by | |||
Property / reviewed by: L'udovít Niepel / rank | |||
Property / reviewed by | |||
Property / reviewed by: L'udovít Niepel / rank | |||
Normal rank | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W1964336531 / rank | |||
Normal rank | |||
Property / arXiv ID | |||
Property / arXiv ID: 0909.1552 / rank | |||
Normal rank |
Revision as of 16:47, 18 April 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Minimum clique partition in unit disk graphs |
scientific article |
Statements
Minimum clique partition in unit disk graphs (English)
0 references
24 January 2012
0 references
The minimum clique partition is known to be an NP-hard problem. The paper presents two algorithms for finding approximate solutions of the clique partition of unit disk graphs. A unit disk graph corresponds to a set of points in the plane. Two vertices are adjacent if and only if the distance between corresponding points is at most \(1\). The first algorithm presented in the article is a polynomial approximation scheme that computes an \((1+\varepsilon)\)-approximation in \(n^{O(1/\varepsilon^2)}\) time. The second algorithm is a randomized version with approximation ratio \(2.16\) and \(O(n^2)\) running time.
0 references
clique partition
0 references
unit disk graph
0 references
approximation algorithm
0 references