Il existe plusieurs classes intéressantes de graphiques avec une largeur d'arbre bornée. Par exemple, les arbres (treewidth 1), les graphes parallèles en série (treewidth 2), les graphes planaires externes (treewidth 2), les graphes -planaires (treewidth O (k)), les graphes de branchwidth...
Décider de l'homomorphisme du graphe est en général NP-complet. Y a-t-il des résultats qui étudient ce problème lorsque les graphiques sous-jacents ont une structure algébrique (tels que la décision d'homomorphismes à partir de graphiques de Cayley ou de cosets Cayley vers d'autres graphiques avec...
Lorsque l'on considère les interactions sur les réseaux, il est généralement très difficile de calculer la dynamique analytiquement , et des approximations sont utilisées. Les approximations de champ moyen finissent généralement par ignorer complètement la structure du réseau, et sont donc rarement...
Les représentations les plus simples pour les graphiques utilisent des matrices / listes d'adjacence, ce qui signifie que chaque nœud et bord est explicitement représenté. L'importance des représentations implicites pour les graphiques présentant de fortes régularités est reconnue depuis longtemps....
Soit . J'ai besoin de générer de simples graphiques G de circonférence g de telle sorte que l'ensemble de tous les g- cycles forme une couverture de double bord de G (c'est-à-dire que chaque bord est partagé par exactement deux g- cycles), et de telle sorte que l'intersection de deux g -cycles est...
Soit une classe héréditaire de graphes. (Hereditary = fermé par rapport à la prise sous - graphes induits.) Soit désignent l'ensemble des graphes de -vertex dans . Disons que contient presque tous les graphes, si la fraction de tous les graphes verticaux tombant dans approche 1, comme .Q n n Q Q n...
Je suis tombé sur deux exemples de dureté hypothétique de certains problèmes graphiques. La dureté hypothétique signifie que réfuter une conjecture impliquerait l'exhaustivité NP du problème de graphe respectif. Par exemple, la conjecture de Barnette déclare que chaque graphe bipartite planaire...
Etant donné le graphique G1, G2 et G3, nous voulons effectuer le test d'isomorphisme F entre G1 et G2 ainsi que G1 et G3. Si G2 et G3 sont très similaires, de sorte que G3 est formé en supprimant un nœud et en insérant un nœud de G2, et nous avons le résultat de F (G1, G2), pouvons-nous calculer F...
La question suivante est liée à l'optimalité de l' algorithme de programmation dynamique Bellman-Ford - plus court (voir cet article pour une connexion). En outre, une réponse positive impliquerait que la taille minimale d'un programme de branchement non déterministe monotone pour le problème...
Un arbre couvrant un graphe est appelé arbre d'exhaustivité si l'ensemble de ses feuilles induit un sous-graphe complet dans le graphe hôte. Étant donné un graphique et un entier k , quelle est la complexité de décider si G contient un arbre d'exhaustivité avec au plus k feuilles?ggGkkkggGkkk Une...
Étant donné un graphe orienté, nous voulons décider s'il contient un cycle orienté de longueur paire. Ce document de 1997 de YUSTER et ZWICK déclare que le problème n'est pas connu pour être en ni pour complet.PPPNPNPNP Y a-t-il un résultat récent qui résout la complexité du problème de cycle pair...
Considérons un graphique connecté non orienté avec des poids de bord non négatifs et deux sommets distincts . Voici quelques problèmes de chemin qui sont tous de la forme suivante: trouver un chemin , de sorte qu'une fonction des poids de bord sur le chemin soit minimale. En ce sens, ils sont tous...
Existe-t-il des classes de graphes agréables pour lesquelles la largeur d'arbre est limitée par une fonction du nombre de cliques ω ( G ) , c'est-à-dire t w ( G ) ≤ f ( ω ( G ) ) ?t w ( G )tw(G)tw(G)ω ( G )ω(G)\omega(G)t w ( G ) ≤ f( ω ( G ) )tw(G)≤f(ω(G))tw(G)\leq f(\omega(G)) Par exemple, c'est...
Je suis tombé sur un problème ouvert posé par David Eppstein et je m'intéresse à son état de complexité. Il a supposé qu'il était NP-complet. Entrée: matrice par de 0 et 1, séquence de 0 et 1nnnnnnn2n2n^2 Question: Existe-t-il un chemin à travers les entrées de matrice adjacentes, couvrant chaque...
Crossposted de MO . l'isomorphisme du graphique coloré (bord) est GI qui préserve les couleurs (des bords s'il est coloré). Il existe plusieurs réductions utilisant des transformations / gadgets de GI (bord) coloré en GI. Pour l'IG de couleur de bord, le plus simple est de remplacer le bord de...
Ce blog parle de générer des "petits labyrinthes sinueux" à l'aide d'un ordinateur et de les énumérer. L'énumération peut être effectuée en utilisant l'algorithme de Wilson pour obtenir l' UST , mais je ne me souviens pas de la formule du nombre.
La complexité de la preuve est l'un des domaines les plus élémentaires de la théorie de la complexité informatique. Un objectif ultime de ce domaine est de prouver , c'est-à-dire que tout prouveur ne peut pas fournir une preuve d'insatisfiabilité d'une formule d'entrée donnée. NP≠ c o...
Je résous un problème de "mélange" d'ensembles d'images qui se chevauchent. Ces ensembles peuvent être représentés par un graphique pondéré non orienté tel que celui-ci: Chaque nœud représente une image. Les images qui se chevauchent sont reliées par un bord. Le poids des bords représente la taille...
Lors de l'introduction de la décomposition modulaire des graphes , la plupart des auteurs utilisent le graphe à 11 sommets, que je copie de wikipedia. La question est de savoir qui en est le concepteur d'origine. (Je ne demande pas qui a dessiné ce graphique pour wikipedia, mais la source originale...
Supposons que j'ai des ensembles avec des éléments pris parmi les r possibles. Chaque ensemble est de taille n ( n < r ), où les ensembles peuvent se chevaucher. Je veux déterminer si les deux problèmes suivants sont NP-complets ou non:PPPrrrnnnn <