Largeur de clique

vignette|upright=1.6|Construction d'un graphe (ici un graphe à distance héréditaire) de largeur de clique 3 par une succession d'unions disjointes, de renommages et de fusions d'étiquettes. Les étiquettes des sommets sont affichées sous forme de couleurs. En théorie des graphes, la largeur de clique d'un graphe est l'un des paramètres qui décrit la complexité structurelle du graphe ; il est étroitement lié à largeur arborescente, mais contrairement à celle-ci, elle peut être bornée même pour des graphes denses . La largeur de clique d'un graphe est le nombre minimum d'étiquettes nécessaires pour construire au moyen des 4 opérations suivantes : Création d'un nouveau sommet v d'étiquette i (noté i(v) ou ) Union disjointe de deux graphes étiquetés G et H (notée ) Jonction par une arête de chaque sommet étiqueté i à chaque sommet étiqueté j (noté η(i,j)), où Renommage de l'étiquette i en étiquette j (notée ρ (i, j) ou ). Dans l’exemple, le graphe final est obtenu par la jonction des trois sommets rouges et des deux sommets verts ; le graphe précédent est l’union disjointe des eux graphes bleu-rouge et vert-bleu, etc. La suite des graphes construits par les opérations est figurée dans l'arbre des opérations. Les graphes de largeur de clique bornée comprennent les cographes et les graphes à distance héréditaire. Il est NP-difficile de calculer la largeur de clique lorsqu'elle n'est pas bornée, et il est inconnu si elle peut être calculée en temps polynomial lorsqu'elle est bornée ; des algorithmes d'approximation efficaces pour la largeur de clique existent. Sur la base de ces algorithmes et du théorème de Courcelle, de nombreux problèmes d'optimisation de graphes qui sont NP-difficiles pour des graphes arbitraires peuvent être résolus ou approximés rapidement sur les graphes de largeur de clique bornée. Les séquences de construction sous-jacentes au concept de largeur de clique ont été formulées par Courcelle, Engelfriet et Rozenberg en 1990 et par Wanke en 1994. Le nom de largeur de clique ("clique-width") a été utilisé pour un concept différent par Chlebíková en 1992 .

À propos de ce résultat

Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.

Publications associées (27)

Personnes associées (4)

Unités associées (2)

Concepts associés (9)

Séances de cours associées (9)

Cographs constitute a small point in the atlas of graph classes. However, by zooming in on this point, we discover a complex world, where many parameters jump from finiteness to infinity. In the present paper, we identify several milestones in the world of ...

ELSEVIER2022

Figlearn: Filter And Graph Learning Using Optimal Transport

Pascal Frossard, Mireille El Gheche, Matthias Minder, Zahra Farsijani

In many applications, a dataset can be considered as a set of observed signals that live on an unknown underlying graph structure. Some of these signals may be seen as white noise that has been filtered on the graph topology by a graph filter. Hence, the k ...

IEEE2021

Distributed Coloring of Graphs with an Optimal Number of Colors

Etienne Michel François Bamas

This paper studies sufficient conditions to obtain efficient distributed algorithms coloring graphs optimally (i.e. with the minimum number of colors) in the LOCAL model of computation. Most of the work on distributed vertex coloring so far has focused on ...

SCHLOSS DAGSTUHL, LEIBNIZ CENTER INFORMATICS2019

vignette| Exemple d'un graphe à distance héréditaire. En théorie des graphes, un graphe à distance héréditaire (aussi appelé graphe complètement séparable) est un graphe dans lequel les distances entre sommets dans tout sous-graphe induit connexe sont les mêmes que celles du graphe tout entier ; autrement dit, tout sous-graphe induit hérite les distances du graphe entier. Les graphes à distance héréditaire ont été nommés et étudiés pour la première fois par Howorka en 1977, alors qu'une classe équivalente de graphes a déjà été considérée en 1970 par Olaru et Sachs qui ont montré que ce sont des graphes parfaits.

Un graphe d'intervalles propre est un graphe d'intervalles possédant une représentation d'intervalles dans laquelle aucun intervalle n'est inclus dans l'autre. Un graphe d'intervalles propre est nécessairement un graphe sans griffe. Soit un graphe possédant une griffe comme sous-graphe induit. On appelle les quatre sommets de la griffe d'intervalles respectives ,, et tels que le sommet soit celui relié aux trois autres et que . Comme la griffe est un graphe induit, , et ne sont pas voisins dans . On a donc .

Un cographe est, en théorie des graphes, un graphe qui peut être généré par complémentation et union disjointe à partir du graphe à un nœud. La plupart des problèmes algorithmiques peuvent être résolus sur cette classe en temps polynomial, et même linaire, du fait de ses propriétés structurelles. Cette famille de graphe a été introduite par plusieurs auteurs indépendamment dans les années 1970 sous divers noms, notamment D*-graphes, hereditary Dacey graphs et 2-parity graphs.

Théorie des graphiques de base MATH-467: Probabilistic methods in combinatorics

Introduit les bases de la théorie des graphes, la théorie de Ramsey et les concepts de coloration des graphes.

Promesse Contrainte Satisfaction et Largeur

Couvertures Promesse Satisfaction Contrainte Problèmes de complexité, de largeur, de coloration des graphiques, de polymorphismes et d'algorithmes.

Programmes d'optimisation : Fonctions de coûts linéaires par pièce MGT-483: Optimal decision making

Couvre la formulation de programmes d'optimisation pour minimiser les fonctions de coûts linéaires à la pièce.