The complexity of generalized clique packing (Q1073049): Difference between revisions

From MaRDI portal
Importer (talk | contribs)
Created a new Item
 
Added link to MaRDI item.
links / mardi / namelinks / mardi / name
 

Revision as of 00:19, 31 January 2024

scientific article
Language Label Description Also known as
English
The complexity of generalized clique packing
scientific article

    Statements

    The complexity of generalized clique packing (English)
    0 references
    1985
    0 references
    It is shown that the problem of packing an arbitrary graph by cliques (with possible intersections) is NP-complete. Let G be a graph. \(K_ i\) denotes a complete subgraph on i vertices, called clique. Let \(p_{ij}(G)\) denote the maximum numbers of cliques \(K_ i\) in G such that any two of them intersect in at most j vertices. The generalized \(P_{ij}\) problem can be formulated as follows: Given graph G and integer k, is \(p_{ij}\) greater than k? It is shown that for \(i\geq 3\) and \(1\leq j\leq i-2\) the \(P_{ij}\) problem is NP-complete. This problem remains still NP-complete even in the case of chordal graphs G.
    0 references
    NP-completeness
    0 references
    clique packing problem
    0 references
    clique intersection
    0 references
    chordal graphs
    0 references

    Identifiers

    0 references
    0 references
    0 references
    0 references
    0 references