Nombre d'intersection

En théorie des graphes, le nombre d'intersection d'un graphe $G=(V,E)$ est le nombre minimal d'éléments nécessaires pour représenter $G$ sous forme de graphe d'intersection d'ensembles finis. Dans cette représentation, chaque sommet correspond à un ensemble et deux sommets sont reliés par une arête dès que leurs ensembles ont un élément commun. Le nombre d'intersection est aussi égal au nombre minimal de cliques (sous-graphes dont les arêtes relient toutes les paires de sommets) nécessaires pour recouvrir toutes les arêtes du graphe $G$ ^[1]^,^[2]. Ce nombre, et le problème associé consistant à le calculer, ont été étudiés sous de nombreux noms alternatifs.

Si ce bandeau n'est plus pertinent, retirez-le. Cliquez ici pour en savoir plus.

La mise en forme de cet article est à améliorer (décembre 2025).

Les applications du nombre d'intersection comprennent l'ordonnancement des opérations sur des ordinateurs à très longs mots d'instruction (Very long instruction word), l'allocation de bande passante dans les réseaux à fibres optiques, la visualisation de données à l'aide d'écrans à lettres compacts, l'analyse des réseaux trophiques en biologie et l'inférence des complexes protéiques à partir des réseaux d'interaction protéine-protéine.

Un graphe avec sommets $n$ et $m$ arêtes a un nombre d'intersection majoré par $\min(m,n^{2}/4)$ . Calculer ou approximer le nombre d'intersection est un problème NP-difficile, mais traitable avec un paramètre fixe.

Terminologie

Les deux formulations équivalentes du nombre d'intersection, en termes de graphes d'intersection ou en termes de cliques qui recouvrent toutes les arêtes, ont été à l'origine de multiples noms pour ce concept et pour le problème informatique de la recherche d'un graphe d'intersection ou d'une couverture par cliques.

Un ensemble de cliques recouvrant toutes les arêtes d'un graphe est appelé Couverture d'arêtes par cliques ^[3] ou simplement Couverture par cliques, bien que ce dernier terme soit ambigu : une couverture de cliques peut également désigner un ensemble de cliques recouvrant tous les sommets du graphe ^[4]. Parfois, le terme « recouvrement » est utilisé à la place de « couverture » ^[5]. Le nombre d'intersection est aussi parfois appelé Nombre de couverture d'arêtes par cliques ^[6] ou Nombre de couverture de cliques ^[7].

Le problème du calcul du nombre d'intersection a été appelé le problème du nombre d'intersection^[8], le problème de la base du graphe d'intersection ^[9], la couverture par cliques^[9], le problème de la couverture d'arêtes par des cliques ^[8], et (en raison de l'une de ses premières applications) le problème du conflit de mots clés^[2].

Définitions

Graphes d'intersection

Soit ${\mathcal {F}}$ être une famille d'ensembles. Le graphe d'intersection de ${\mathcal {F}}$ est un graphe non orienté qui possède un sommet pour chaque ensemble de ${\mathcal {F}}$ et une arête entre chaque paire d'ensembles ayant une intersection non vide. Tout graphe peut être représenté comme un graphe d'intersection de cette manière^[10].

Le nombre d'intersection d'un graphe $G$ est le plus petit nombre telle qu'il existe une représentation de ce type pour laquelle l'union des ensembles dans ${\mathcal {F}}$ a $k$ éléments^[9].

Couverture d'arêtes par cliques

Le nombre d'intersection d'un graphe est aussi défini comme le plus petit nombre de cliques dans $G$ ( sous-graphes complets de $G$ ) qui recouvrent toutes les arêtes de $G$ ^[1]^,^[11]. Un ensemble de cliques possédant cette propriété est appelé « couverture d'arêtes par cliques » et pour cette raison, le nombre d'intersection est aussi parfois appelé « nombre de couverture d'arêtes par cliques »^[6].

Équivalence

L'égalité du nombre d'intersections et du nombre de couvertures d'arêtes par cliques admet une démonstration concise.

D'une part, supposons que $G$ soit le graphe d'intersection d'une famille ${\mathcal {F}}$ d'ensembles dont l'union $U$ a $k$ éléments. Pour chaque élément $x\in U$ , les ensembles dans ${\mathcal {F}}$ qui contiennent $x$ forment une clique $K_{x}$ dans $G$ , car ces ensembles possède (deux à deux) une intersection non vide contenant $x$ . De plus, les cliques ainsi formées recouvrent chaque arête dans $G$ : si deux ensembles dans ${\mathcal {F}}$ ont une intersection non vide alors il existe une arête entre ces deux ensembles et cette arête est contenue dans la clique $K_{x}$ pour chaque élément $x$ qui appartient à leur intersection. Par conséquent, les arêtes de $G$ peut être couvert par $k$ cliques, une par élément de $U$ ^[11].

Réciproquement, si les arêtes du graphe $G$ peuvent être couvertes par $k$ cliques, alors chaque sommet $v$ de $G$ peut être représenté par l'ensemble des cliques de cette couverture qui contiennent $v$ . Deux de ces ensembles de cliques, pour deux sommets $u$ et $v$ , ont une intersection non vide si et seulement s'il existe une clique dans la couverture qui contient à la fois $u$ et $v$ . Si cette clique contenant $u$ et $v$ existe, alors elle contient également l'arête $uv$ , qui est une arête de $G$ . Inversement, si $uv$ est une arête dans $G$ , alors elle est couverte par une clique ; cette clique contient à la fois $u$ et $v$ , elle appartient donc à l'intersection des ensembles de cliques qui représentent $u$ et $v$ . Par conséquent, une couverture par des cliques conduit à une représentation d'intersection avec $k$ éléments^[11].

Applications

La représentation abstraite d'un graphe comme un graphe d'intersection d'ensembles peut être utilisée pour construire des représentations géométriques d'intersection plus concrètes de ce même graphe. En particulier, si un graphe possède un nombre d'intersection $k$ , il peut être représenté comme un graphe d'intersection de $k$ hypersphères unitaires de dimension n. La dimension minimale des hypersphères dans une telle représentation est appelée sphéricité d'un graphe, de sorte que la sphéricité est inférieure ou égale au nombre d'intersection^[6].

Un recouvrement par cliques peut servir de schéma d'étiquetage d'adjacence pour un graphe. Chaque sommet est étiqueté par une valeur binaire, permettant de tester rapidement l'existence d'une arête entre deux sommets en comparant leurs valeurs. Ces étiquettes comportent un bit par clique : zéro si le sommet n'appartient pas à la clique, un s'il y appartient. Avec ce schéma, deux sommets sont adjacents si et seulement si la valeur binaire de leurs étiquettes est non nulle. La longueur des étiquettes correspond au nombre d'intersection du graphe. Lorsque cette longueur est faible, une représentation informatique du graphe utilisant uniquement ces étiquettes consomme moins de mémoire que les méthodes explicites telles que les listes d'adjacence et permet des tests d'adjacence plus rapides. Cette méthode a été utilisée par E. Kellerman d'IBM dans une des premières applications des nombres d'intersection, pour étiqueter un ensemble de mots-clés et détecter rapidement les conflits. C’est pourquoi le problème du calcul des nombres d’intersection est également appelé problème de conflit de mots-clés^[12]^,^[13]. De même, en géométrie algorithmique, les représentations basées sur le nombre d’intersection ont été considérées comme une représentation compacte pour les graphes de visibilité, bien qu’il existe des entrées géométriques pour lesquelles cette représentation nécessite un nombre de cliques quasi quadratique^[14].

Bornes supérieures

Tout graphe ayant $m$ arêtes a un nombre d'intersection majoré par $m$ . Cela découle de l'observation que chaque arête est elle-même une clique à deux sommets. Il y a $m$ de ces cliques, et ensemble elles recouvrent tous les bords, formant ainsi une couverture d'arêtes par cliques de taille $m$ ^[15].

En outre, tout graphe ayant $n$ sommets a un nombre d'intersection majoré par $\lfloor n^{2}/4\rfloor$ . Un résultat plus fort est que les arêtes d'un graphe à $n$ sommets peut être couvert par au plus $\lfloor n^{2}/4\rfloor$ cliques, chacune étant soit une arête simple, soit un triangle. Un algorithme glouton peut trouver cette couverture en supprimant deux sommets adjacents et en s'appelant récursivement sur le graphe restant. Après avoir rétabli les deux sommets supprimés, l'algorithme ajoute à la couverture chaque triangle auquel ils appartiennent, ce qui couvre toutes les arêtes les reliant à des voisins communs. Toutes les arêtes restantes reliant l'un des deux sommets supprimés à un de leurs voisins, sans former de triangle, sont couvertes par des cliques de deux sommets. S'il n'y a pas de triangle contenant les deux sommets supprimés, l'arête entre eux est également couverte par une clique de deux sommets. Par hypothèse de récurrence, la couverture du graphe après suppression des deux sommets comporte au plus $\lfloor (n-2)^{2}/4\rfloor$ cliques. Les deux sommets supprimés appartiennent à au plus $n-1$ autres cliques, il y a égalité lorsque tous les autres sommets sont des voisins non partagés et que l'arête entre les deux sommets doit être utilisée comme clique. L'addition de ces deux quantités donne $\lfloor n^{2}/4\rfloor$ cliques au total^[2]^,^[11]. Ceci généralise le théorème de Mantel selon lequel un graphe sans triangle possède au plus $\lfloor n^{2}/4\rfloor$ arêtes, car dans un graphe sans triangle, la seule couverture optimale d'arêtes par cliques a une clique par arête et donc le nombre d'intersections est égal au nombre d'arêtes^[2].

Une borne encore plus précise est possible lorsque le nombre d'arêtes est strictement supérieur à ${\tfrac {n^{2}}{4}}$ . On note $p$ le nombre de paires de sommets non reliés par une arête dans un graphe $G$ donné et $t$ l'unique entier pour lequel $(t-1)t\leq p<t(t+1)$ . Alors le nombre d'intersection de $G$ est au plus $p+t$ ^[2]^,^[16]. Les graphes qui sont complémentaires d'un graphe creux ont de petits nombres d'intersection : le nombre d'intersection de tout graphe $G$ à $n$ sommets est au plus $2e^{2}(d+1)^{2}\ln n$ , où $e$ est la base du logarithme naturel et $d$ est le degré maximal du graphe complémentaire de $G$ ^[5].

Il ressort des résultats sur la structure des graphes sans étoile que, lorsqu'un graphe sans étoile connexe à $n$ sommets possède au moins trois sommets indépendants, il a un nombre d'intersection inférieur ou égal à $n$ . Il reste à déterminer si cela est vrai pour tous les graphes sans étoile sans qu'ils possèdent nécessairement de grands ensembles indépendants^[7]. Les graphes adjoints (line graph), qui représentent les arêtes et les paires d'arêtes tangentes d'un autre graphe $G$ , constituent une sous-classe importante des graphes sans étoile. Une couverture optimale de cliques d'un graphe adjoint $L(G)$ peut être formé avec une clique pour chaque triangle dans $G$ qui possède deux ou trois sommets de degré 2, et une clique pour chaque sommet de degré au moins deux qui n'est pas un sommet de degré deux de l'un de ces triangles. Le nombre d'intersection est le nombre de cliques de ces deux types^[17].

Dans le modèle Erdős – Rényi – Gilbert de graphes aléatoires, dans lequel tous les graphes à $n$ sommets étiquetés sont équiprobables (ou, de manière équivalente, chaque arête est présente ou absente, indépendamment des autres arêtes, avec une probabilité ${\tfrac {1}{2}}$ ), le numéro d'intersection d'un graphe aléatoire à n sommets est, avec une forte probabilité à un facteur constant près, de ${\frac {n^{2}}{\log ^{2}n}},$ Cette valeur est plus petite d'un facteur de $\log ^{2}n$ que le nombre d'arêtes. Dans ces graphes, les cliques maximales possèdent (avec une forte probabilité) un nombre logarithmique de sommets, ce qui implique qu'il en faut autant pour couvrir toutes les arêtes. L'autre sens de la borne consiste à prouver qu'il est possible de trouver suffisamment de cliques de taille logarithmique pour couvrir la plupart des arêtes, les arêtes restantes pouvant être couvertes par des cliques à deux sommets^[18]^,^[19].

Les premières recherches sur les nombres d'intersection consistaient en grande partie à calculer ce nombre pour divers graphes spécifiques, tels que les graphes formés en supprimant un sous-graphe complet ou bine en supprimant un couplage parfait d'un graphe complet plus grand^[20].

Complexité

Tester si un graphe $G$ a un nombre d'intersection inférieur ou égale à $k$ est un problème NP-complet^[9]^,^[17]^,^[13]. Par conséquent, calculer le nombre d'intersection d'un graphe donné est également NP-difficile. La difficulté du calcul du nombre d'intersections a été utilisée pour prouver que reconnaître les carrés des graphes scindés est NP-complet^[21].

Le problème du calcul du nombre d'intersection est cependant traitable à paramètre fixé : c'est-à-dire qu'il peut être résolu en un temps borné par un polynôme en $n$ multiplié par une fonction en $k$ , le nombre d'intersection. Cela peut être démontré en observant qu'il y a au plus $2^{k}$ des voisinages fermés distincts (le voisinage fermé d'un sommet est l'ensemble des voisins de ce sommets avec le sommet étudié). Or deux sommets appartenant à la même clique ont le même voisinage. Le graphe obtenu en sélectionnant un sommet par voisinage fermé possède le même nombre d'intersection que le graphe original^[4]^,^[22]. Par conséquent, en temps polynomial, l'entrée peut être réduite à un noyau plus petit avec au plus ${\textstyle 2^{k}}$ sommets. Appliquer une recherche exhaustive sur au plus $2^{k}!$ possibilités d'ensembles distincts de cliques aux sommets restants donne un temps doublement exponentiel en $k$ ^[4]^,^[23]. La dépendance doublement exponentielle sur $k$ ne peut pas être réduite à une simple exponentielle par une réduction au noyau de taille polynomiale, sauf si la hiérarchie polynomiale s'effondre ^[24]. Si l' hypothèse du temps exponentiel est vérifiée, une double dépendance exponentielle est nécessaire, que la noyau soit réduit ou non ^[23]. Sur les graphes de largeur arborescente bornée, la programmation dynamique sur une décomposition arborescente du graphe permet de trouver le nombre d'intersection en temps linéaire ^[25]^,^[26].

Des algorithmes plus efficaces sont connus pour certaines classes particulières de graphes. Le nombre d'intersection d'un graphe d'intervalles est toujours égal à son nombre de cliques maximales, calculable en temps polynomial^[27]^,^[28]. Plus généralement, pour les graphes cordaux, le nombre d'intersection peut être calculé par un algorithme qui considère les sommets dans un ordre d'élimination du graphe (un ordre dans lequel chaque sommet et ses voisins ultérieurs forment une clique). Pour chaque sommet $v$ , on forme une clique pour $v$ et ses voisins ultérieurs chaque fois qu'au moins une des arêtes incidentes à $v$ n'est couverte par aucune clique antérieure^[28]. Il est également possible de trouver le nombre d'intersections en temps linéaire dans les graphes d'arcs circulaires^[29]. Cependant, bien que ces graphes ne possèdent qu'un nombre polynomial de cliques possibles pour la couverture, le fait d'avoir peu de cliques ne suffit pas à simplifier le problème : il existe des familles de graphes avec un nombre polynomial de cliques pour lesquelles le calcul du nombre d'intersection reste NP-difficile^[8]. Le nombre d'intersection peut cependant être trouvé en temps polynomial pour les graphes dont le degré maximal est cinq, mais est NP-difficile pour les graphes de degré maximal six^[30]^,^[31]. Sur les graphes planaires, le calcul exact du nombre d'intersections reste NP-difficile, mais il existe un schéma d'approximation en temps polynomial basé sur la technique de Baker^[26].

Références

1 2 (en) Jonathan L. Gross et Yellen, Graph Theory and its Applications, CRC Press, 2006 (ISBN 978-1-58488-505-4), p. 440.
1 2 3 4 5 Fred S. Roberts, « Applications of edge coverings by cliques », Discrete Applied Mathematics, vol. 10, n^o 1,‎ 1985, p. 93–109 (DOI 10.1016/0166-218X(85)90061-7, MR 770871)
↑ F.B. Shepherd et A. Vetta, « Lighting fibers in a dark network », IEEE Journal on Selected Areas in Communications, vol. 22, n^o 9,‎ novembre 2004, p. 1583–1588 (DOI 10.1109/jsac.2004.833850, Bibcode 2004IJSAC..22.1583S, S2CID 31868129, lire en ligne [archive du 20 septembre 2022])
1 2 3 Jens Gramm, Jiong Guo, Falk Hüffner et Rolf Niedermeier, « Data reduction and exact algorithms for clique cover », Journal of Experimental Algorithmics, vol. 13, n^o 2,‎ 2009, p. 2–15 (DOI 10.1145/1412228.1412236, S2CID 15057639, lire en ligne)
1 2 Noga Alon, « Covering graphs by the minimum number of equivalence relations », Combinatorica, vol. 6, n^o 3,‎ 1986, p. 201–206 (DOI 10.1007/bf02579381, S2CID 13522339, lire en ligne)
1 2 3 T. S. Michael et Thomas Quint, « Sphericity, cubicity, and edge clique covers of graphs », Discrete Applied Mathematics, vol. 154, n^o 8,‎ 2006, p. 1309–1313 (DOI 10.1016/j.dam.2006.01.004). In 2009, the authors released an erratum, noting that theorem 4 of this paper, on cubicity, is erroneous. Their results on sphericity are unaffected.
1 2 Ramin Javadi et Sepehr Hajebi, « Edge clique cover of claw-free graphs », Journal of Graph Theory, vol. 90, n^o 3,‎ 2019, p. 311–405 (DOI 10.1002/jgt.22403, MR 3904838, arXiv 1608.07723, S2CID 67770018)
1 2 3 Bill Rosgen et Lorna Stewart, « Complexity results on graphs with few cliques », Discrete Mathematics & Theoretical Computer Science, vol. 9, n^o 1,‎ 2007, p. 127–135 (DOI 10.46298/dmtcs.387 , MR 2335890, lire en ligne)
1 2 3 4 Michael R. Garey et David S. Johnson., « Problems GT17 (covering by cliques) and GT59 (intersection graph basis) », dans Computers and Intractability: A Guide to the Theory of NP-Completeness, New York, W.H. Freeman, 1979.
↑ Edward Szpilrajn-Marczewski, « Sur deux propriétés des classes d'ensembles », Fundamenta Mathematicae, vol. 33,‎ 1945, p. 303–307 (DOI 10.4064/fm-33-1-303-307 , MR 15448)
1 2 3 4 Paul Erdős, A. W. Goodman et Louis Pósa, « The representation of a graph by set intersections », Canadian Journal of Mathematics, vol. 18, n^o 1,‎ 1966, p. 106–112 (DOI 10.4153/CJM-1966-014-3, MR 0186575, S2CID 646660, CiteSeer^x 10.1.1.210.6950, lire en ligne)
↑ E. Kellerman, « Determination of keyword conflict », IBM Technical Disclosure Bulletin, vol. 16, n^o 2,‎ 1973, p. 544–546, as cited by Kou, Stockmeyer et Wong 1978
1 2 L. T. Kou, L. J. Stockmeyer et C. K. Wong, « Covering edges by cliques with regard to keyword conflicts and intersection graphs », Communications of the ACM, vol. 21, n^o 2,‎ 1978, p. 135–139 (DOI 10.1145/359340.359346 , S2CID 15059696)
↑ P. K. Agarwal, N. Alon, B. Aronov et S. Suri, « Can visibility graphs be represented compactly? », Discrete & Computational Geometry, vol. 12, n^o 3,‎ 1994, p. 347–365 (DOI 10.1007/BF02574385 , MR 1298916)
↑ V. K. Balakrishnan, Schaum's Outline of Theory and Problems of Graph Theory, McGraw-Hill Professional, 1997 (ISBN 978-0-07-005489-9), p. 40
↑ L. Lovász, « On covering of graphs », dans Proceedings of the Colloquium held at Tihany, Hungary, 1966, Academic Press, 1968, 231–236 p..
1 2 J. Orlin, « Contentment in graph theory: covering graphs with cliques », Indagationes Mathematicae, vol. 80, n^o 5,‎ 1977, p. 406–424 (DOI 10.1016/1385-7258(77)90055-5)
↑ Béla Bollobás, Paul Erdős, Joel Spencer et Douglas B. West, « Clique coverings of the edges of a random graph », Combinatorica, vol. 13, n^o 1,‎ 1993, p. 1–5 (DOI 10.1007/BF01202786, MR 1221173, S2CID 26565829, lire en ligne)
↑ Alan Frieze et Bruce Reed, « Covering the edges of a random graph by cliques », Combinatorica, vol. 15, n^o 4,‎ 1995, p. 489–497 (DOI 10.1007/BF01192522, MR 1364022, arXiv 1103.4870, S2CID 7326662)
↑ Norman J. Pullman, « Clique coverings of graphs — A survey », dans Combinatorial Mathematics X: Proceedings of the Conference Held in Adelaide, Australia, August 23-27, 1982, vol. 1036, Springer, coll. « Lecture Notes in Mathematics », 1983, 72–85 p. (ISBN 978-3-540-12708-6, DOI 10.1007/bfb0071509, MR 0731572)
↑ Lap Chi Lau et Derek G. Corneil, « Recognizing powers of proper interval, split, and chordal graphs », SIAM Journal on Discrete Mathematics, vol. 18, n^o 1,‎ 2004, p. 83–102 (DOI 10.1137/S0895480103425930, MR 2112490)
↑ A. Gyárfás, « A simple lower bound on edge coverings by cliques », Discrete Mathematics, vol. 85, n^o 1,‎ 1990, p. 103–104 (DOI 10.1016/0012-365X(90)90168-H , MR 1078317)
1 2 Marek Cygan, Marcin Pilipczuk et Michał Pilipczuk, « Known algorithms for edge clique cover are probably optimal », SIAM Journal on Computing, vol. 45, n^o 1,‎ 2016, p. 67–83 (DOI 10.1137/130947076, MR 3448348, arXiv 1203.1754, S2CID 11264145)
↑ Marek Cygan, Stefan Kratsch, Marcin Pilipczuk, Michal Pilipczuk et Magnus Wahlström, « Clique cover and graph separation: new incompressibility results », ACM Transactions on Computation Theory, vol. 6, n^o 2,‎ 2014, p. 6:1–6:19 (DOI 10.1145/2594439, S2CID 6887887, lire en ligne)
↑ Hans L. Bodlaender et Babette van Antwerpen-de Fluiter, « Reduction algorithms for graphs of small treewidth », Information and Computation, vol. 167, n^o 2,‎ 2001, p. 86–119 (DOI 10.1006/inco.2000.2958 , MR 1835592)
1 2 Mathieu Blanchette, Ethan Kim et Adrian Vetta, « Clique Cover on Sparse Networks », dans Proceedings of the 14th Meeting on Algorithm Engineering & Experiments, ALENEX 2012, The Westin Miyako, Kyoto, Japan, January 16, 2012, Society for Industrial and Applied Mathematics, 2012, 93–102 p. (ISBN 978-1-61197-212-2, DOI 10.1137/1.9781611972924.10)
↑ R. J. Opsut et F. S. Roberts, « On the fleet maintenance, mobile radio frequency, task assignment, and traffic phasing problems », dans The theory and applications of graphs, New York, Wiley, 1981, 479–492 p. (ISBN 0-471-08473-5, MR 634549); as cited by Roberts 1985
1 2 Edward R. Scheinerman et Ann N. Trenk, « On the fractional intersection number of a graph », Graphs and Combinatorics, vol. 15, n^o 3,‎ 1999, p. 341–351 (DOI 10.1007/s003730050068, MR 1723018, S2CID 33081703)
↑ Wen Lian Hsu et Kuo-Hui Tsai, « Linear time algorithms on circular-arc graphs », Information Processing Letters, vol. 40, n^o 3,‎ 1991, p. 123–129 (DOI 10.1016/0020-0190(91)90165-E, MR 1143909)
↑ Norman J. Pullman, « Clique covering of graphs, IV: Algorithms », SIAM Journal on Computing, vol. 13, n^o 1,‎ 1984, p. 57–75 (DOI 10.1137/0213005, MR 731027)
↑ D. N. Hoover, « Complexity of graph covering problems for graphs of low degree », Journal of Combinatorial Mathematics and Combinatorial Computing, vol. 11,‎ 1992, p. 187–208 (MR 1160076)

Portail des mathématiques

[gy06-1] 1 2 (en) Jonathan L. Gross et Yellen, Graph Theory and its Applications, CRC Press, 2006 (ISBN 978-1-58488-505-4), p. 440.

[r85-2] 1 2 3 4 5 Fred S. Roberts, « Applications of edge coverings by cliques », Discrete Applied Mathematics, vol. 10, n^o 1,‎ 1985, p. 93–109 (DOI 10.1016/0166-218X(85)90061-7, MR 770871)

[sv04-3] F.B. Shepherd et A. Vetta, « Lighting fibers in a dark network », IEEE Journal on Selected Areas in Communications, vol. 22, n^o 9,‎ novembre 2004, p. 1583–1588 (DOI 10.1109/jsac.2004.833850, Bibcode 2004IJSAC..22.1583S, S2CID 31868129, lire en ligne [archive du 20 septembre 2022])

[gghn09-4] 1 2 3 Jens Gramm, Jiong Guo, Falk Hüffner et Rolf Niedermeier, « Data reduction and exact algorithms for clique cover », Journal of Experimental Algorithmics, vol. 13, n^o 2,‎ 2009, p. 2–15 (DOI 10.1145/1412228.1412236, S2CID 15057639, lire en ligne)

[a86-5] 1 2 Noga Alon, « Covering graphs by the minimum number of equivalence relations », Combinatorica, vol. 6, n^o 3,‎ 1986, p. 201–206 (DOI 10.1007/bf02579381, S2CID 13522339, lire en ligne)

[mtq06-6] 1 2 3 T. S. Michael et Thomas Quint, « Sphericity, cubicity, and edge clique covers of graphs », Discrete Applied Mathematics, vol. 154, n^o 8,‎ 2006, p. 1309–1313 (DOI 10.1016/j.dam.2006.01.004). In 2009, the authors released an erratum, noting that theorem 4 of this paper, on cubicity, is erroneous. Their results on sphericity are unaffected.

[jh19-7] 1 2 Ramin Javadi et Sepehr Hajebi, « Edge clique cover of claw-free graphs », Journal of Graph Theory, vol. 90, n^o 3,‎ 2019, p. 311–405 (DOI 10.1002/jgt.22403, MR 3904838, arXiv 1608.07723, S2CID 67770018)

[rs07-8] 1 2 3 Bill Rosgen et Lorna Stewart, « Complexity results on graphs with few cliques », Discrete Mathematics & Theoretical Computer Science, vol. 9, n^o 1,‎ 2007, p. 127–135 (DOI 10.46298/dmtcs.387 , MR 2335890, lire en ligne)

[gj79-9] 1 2 3 4 Michael R. Garey et David S. Johnson., « Problems GT17 (covering by cliques) and GT59 (intersection graph basis) », dans Computers and Intractability: A Guide to the Theory of NP-Completeness, New York, W.H. Freeman, 1979.

[sm45-10] Edward Szpilrajn-Marczewski, « Sur deux propriétés des classes d'ensembles », Fundamenta Mathematicae, vol. 33,‎ 1945, p. 303–307 (DOI 10.4064/fm-33-1-303-307 , MR 15448)

[egp66-11] 1 2 3 4 Paul Erdős, A. W. Goodman et Louis Pósa, « The representation of a graph by set intersections », Canadian Journal of Mathematics, vol. 18, n^o 1,‎ 1966, p. 106–112 (DOI 10.4153/CJM-1966-014-3, MR 0186575, S2CID 646660, CiteSeer^x 10.1.1.210.6950, lire en ligne)

[k73-12] E. Kellerman, « Determination of keyword conflict », IBM Technical Disclosure Bulletin, vol. 16, n^o 2,‎ 1973, p. 544–546, as cited by Kou, Stockmeyer et Wong 1978

[ksw78-13] 1 2 L. T. Kou, L. J. Stockmeyer et C. K. Wong, « Covering edges by cliques with regard to keyword conflicts and intersection graphs », Communications of the ACM, vol. 21, n^o 2,‎ 1978, p. 135–139 (DOI 10.1145/359340.359346 , S2CID 15059696)

[aaas94-14] P. K. Agarwal, N. Alon, B. Aronov et S. Suri, « Can visibility graphs be represented compactly? », Discrete & Computational Geometry, vol. 12, n^o 3,‎ 1994, p. 347–365 (DOI 10.1007/BF02574385 , MR 1298916)

[b97-15] V. K. Balakrishnan, Schaum's Outline of Theory and Problems of Graph Theory, McGraw-Hill Professional, 1997 (ISBN 978-0-07-005489-9), p. 40

[l68-16] L. Lovász, « On covering of graphs », dans Proceedings of the Colloquium held at Tihany, Hungary, 1966, Academic Press, 1968, 231–236 p..

[o77-17] 1 2 J. Orlin, « Contentment in graph theory: covering graphs with cliques », Indagationes Mathematicae, vol. 80, n^o 5,‎ 1977, p. 406–424 (DOI 10.1016/1385-7258(77)90055-5)

[besw93-18] Béla Bollobás, Paul Erdős, Joel Spencer et Douglas B. West, « Clique coverings of the edges of a random graph », Combinatorica, vol. 13, n^o 1,‎ 1993, p. 1–5 (DOI 10.1007/BF01202786, MR 1221173, S2CID 26565829, lire en ligne)

[fr95-19] Alan Frieze et Bruce Reed, « Covering the edges of a random graph by cliques », Combinatorica, vol. 15, n^o 4,‎ 1995, p. 489–497 (DOI 10.1007/BF01192522, MR 1364022, arXiv 1103.4870, S2CID 7326662)

[p83-20] Norman J. Pullman, « Clique coverings of graphs — A survey », dans Combinatorial Mathematics X: Proceedings of the Conference Held in Adelaide, Australia, August 23-27, 1982, vol. 1036, Springer, coll. « Lecture Notes in Mathematics », 1983, 72–85 p. (ISBN 978-3-540-12708-6, DOI 10.1007/bfb0071509, MR 0731572)

[lc04-21] Lap Chi Lau et Derek G. Corneil, « Recognizing powers of proper interval, split, and chordal graphs », SIAM Journal on Discrete Mathematics, vol. 18, n^o 1,‎ 2004, p. 83–102 (DOI 10.1137/S0895480103425930, MR 2112490)

[g90-22] A. Gyárfás, « A simple lower bound on edge coverings by cliques », Discrete Mathematics, vol. 85, n^o 1,‎ 1990, p. 103–104 (DOI 10.1016/0012-365X(90)90168-H , MR 1078317)

[cpp16-23] 1 2 Marek Cygan, Marcin Pilipczuk et Michał Pilipczuk, « Known algorithms for edge clique cover are probably optimal », SIAM Journal on Computing, vol. 45, n^o 1,‎ 2016, p. 67–83 (DOI 10.1137/130947076, MR 3448348, arXiv 1203.1754, S2CID 11264145)

[ckppw14-24] Marek Cygan, Stefan Kratsch, Marcin Pilipczuk, Michal Pilipczuk et Magnus Wahlström, « Clique cover and graph separation: new incompressibility results », ACM Transactions on Computation Theory, vol. 6, n^o 2,‎ 2014, p. 6:1–6:19 (DOI 10.1145/2594439, S2CID 6887887, lire en ligne)

[bf01-25] Hans L. Bodlaender et Babette van Antwerpen-de Fluiter, « Reduction algorithms for graphs of small treewidth », Information and Computation, vol. 167, n^o 2,‎ 2001, p. 86–119 (DOI 10.1006/inco.2000.2958 , MR 1835592)

[bkv12-26] 1 2 Mathieu Blanchette, Ethan Kim et Adrian Vetta, « Clique Cover on Sparse Networks », dans Proceedings of the 14th Meeting on Algorithm Engineering & Experiments, ALENEX 2012, The Westin Miyako, Kyoto, Japan, January 16, 2012, Society for Industrial and Applied Mathematics, 2012, 93–102 p. (ISBN 978-1-61197-212-2, DOI 10.1137/1.9781611972924.10)

[or81-27] R. J. Opsut et F. S. Roberts, « On the fleet maintenance, mobile radio frequency, task assignment, and traffic phasing problems », dans The theory and applications of graphs, New York, Wiley, 1981, 479–492 p. (ISBN 0-471-08473-5, MR 634549); as cited by Roberts 1985

[st99-28] 1 2 Edward R. Scheinerman et Ann N. Trenk, « On the fractional intersection number of a graph », Graphs and Combinatorics, vol. 15, n^o 3,‎ 1999, p. 341–351 (DOI 10.1007/s003730050068, MR 1723018, S2CID 33081703)

[ht91-29] Wen Lian Hsu et Kuo-Hui Tsai, « Linear time algorithms on circular-arc graphs », Information Processing Letters, vol. 40, n^o 3,‎ 1991, p. 123–129 (DOI 10.1016/0020-0190(91)90165-E, MR 1143909)

[p84-30] Norman J. Pullman, « Clique covering of graphs, IV: Algorithms », SIAM Journal on Computing, vol. 13, n^o 1,‎ 1984, p. 57–75 (DOI 10.1137/0213005, MR 731027)

[h92-31] D. N. Hoover, « Complexity of graph covering problems for graphs of low degree », Journal of Combinatorial Mathematics and Combinatorial Computing, vol. 11,‎ 1992, p. 187–208 (MR 1160076)

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21]

[22]

[23]

[24]

[25]

[26]

[27]

[28]

[29]

[30]

[31]