Minimum clique partition in unit disk graphs (Q659693): Difference between revisions

From MaRDI portal
Import240304020342 (talk | contribs)
Set profile property.
Importer (talk | contribs)
Changed an Item
 
(One intermediate revision by one other user not shown)
Property / OpenAlex ID
 
Property / OpenAlex ID: W1964336531 / rank
 
Normal rank
Property / arXiv ID
 
Property / arXiv ID: 0909.1552 / rank
 
Normal rank

Latest 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
    0 references
    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
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    clique partition
    0 references
    unit disk graph
    0 references
    approximation algorithm
    0 references
    0 references
    0 references