Greedy maximum-clique decompositions (Q1340141)
From MaRDI portal
 | This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: Greedy maximum-clique decompositions |
scientific article; zbMATH DE number 700955
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | Greedy maximum-clique decompositions |
scientific article; zbMATH DE number 700955 |
Statements
Greedy maximum-clique decompositions (English)
0 references
18 May 1995
0 references
Consider a clique decomposition of a graph on \(n\) vertices obtained by removing maximum cliques one by one. The author proves that then the sum of the number of vertices in all the cliques in this decomposition is at most \(n^ 2/2\).
0 references
clique decomposition
0 references
maximum cliques
0 references
0.8837108016014099
0 references
0.8680681586265564
0 references
