Étant donné un graphe en accords

Un graphe est en corde s'il n'a pas de cycles induits de longueur ou plus. Un arbre de clique de est un arbre dont les sommets de l'arbre sont les cliques maximales de . Une arête en correspond à un séparateur minimal. Le nombre d'arbres cliques distincts peut être exponentiel dans le nombre de sommets dans un graphique en accords.$G$$4$$T$$G$$G$$T$

Le graphique clique réduit est l'union de tous les arbres de la clique de . Autrement dit, il a tous les mêmes sommets et toutes les arêtes possibles. Quelle est la complexité du calcul de pour un donné ?$C_r(G)$$G$$C_r(G)$$G$

Je pense avoir vu une fois une présentation affirmant que peut être calculé en temps O ( m + n ) sans preuve. Cela signifie qu'il est aussi facile que le calcul d' un arbre de clique de G . Existe-t-il une référence qui confirme cela ou donne un algorithme plus lent pour le calculer?$C_r(G)$$O(m+n)$$G$

La complexité est O (nm) ... à partir de G, calculez les cliques maximales et faites-en des sommets dans votre graphique H (initialement sans arêtes) ... puis calculez tous les séparateurs minimaux et triez-les par taille ... choisissez le plus grand séparateur S et faites deux cliques C, C 'adjacentes à H (connectez-les par une arête avec l'étiquette S) si C, C' contiennent toutes deux S et sont dans différentes composantes connectées de H (au départ, cela est bien sûr toujours vrai, mais peut pas plus tard) ... puis choisissez le plus grand séparateur suivant et faites de même ... répétez jusqu'à ce que tous les séparateurs soient traités ... le graphique résultant H est le graphique de clique réduit de G ... le calcul des cliques maximales et des séparateurs minimaux prend O (n + m) ... il y a O (n) cliques et O (n) séparateurs ... le reste de la construction est O (nm) car le traitement de chaque séparateur peut prendre O (m) temps ... .. .cela ne peut pas être amélioré en dessous de O (n ^ 2) sauf si vous pouvez résoudre le problème suivant: étant donné un graphique G trouver deux sommets u, v tels que N (u) contient N (v) ... ce dernier n'est pas connu pour avoir Solution O (n + m) ... ... il est donc peu probable qu'un algorithme O (n + m) pour le calcul des graphes de cliques réduits soit possible ...

voir la section 5 de M. Habib, J. Stacho: Algorithme en temps polynomial pour le feuilletage des graphiques en accords, In: Algorithms - ESA 2009, Lecture Notes in Computer Science 5757/2009, pp. 290-300. ( http://www.cs.toronto.edu/~stacho/public/leafage-esa1.pdf )