Je recherche des problèmes connus pour être des PNJ pour les graphes dirigés mais qui ont un algorithme polynomial pour les graphes non orientés. J'ai vu la question concernant l'inverse des problèmes «dirigés» qui sont plus faciles que leur variante «non dirigée» , mais je recherche la dureté du...
Prenez un graphe orienté où les bords sont décorés d'un nombre naturel. On veut l'ensemble de tous les chemins entre deux sommets et telle sorte que chaque bord successif du chemin soit décoré d'un nombre naturel supérieur au nombre naturel décorant le bord précédent.ggGPPPv1v1v_1v2v2v_2 Une...
Étant donné un simple graphe non orienté GGG , trouver un sous-ensemble A≠∅A≠∅A\neq \emptyset de sommets, tel que pour tout sommet x∈Ax∈Ax\in A au moins la moitié des voisins de xxx sont également dans AAA , et la taille de AAA est minimale. Autrement dit, nous recherchons un cluster, dans lequel...
Un graphique mixte est un graphique qui peut avoir à la fois des bords orientés et non orientés. Son graphe non orienté sous-jacent est obtenu en oubliant les orientations des arêtes dirigées, et dans l'autre sens, une orientation d'un graphe mixte est obtenue en affectant une direction à chaque...
Une extension classique du problème du débit maximal est le problème du "débit maximal dans le temps": on vous donne un digraphe, dont deux nœuds sont distingués comme source et puits, où chaque arc a deux paramètres, une capacité par -unité et un délai. Vous avez également un horizon de temps ....
Il y a environ un an, un ami et moi avons pensé à un moyen d'implémenter l'algorithme de Kruskal pour des graphiques denses mieux que la limite habituelle O ( m logm )O(mJournalm)O(m \log m)(sans supposer des arêtes pré-triées). Plus précisément, nous atteignons Θ ( n2)Θ(n2)\Theta(n^2) dans tous...
∑X∏i j ∈ EF( xje, xj)∑X∏jej∈EF(Xje,Xj)\sum_x \prod_{ij \in E} f(x_i,x_j)maxX∏i j ∈ EF( xje, xj)maxX∏jej∈EF(Xje,Xj)\max_x \prod_{ij \in E} f(x_i,x_j) Lorsque max ou sum est pris sur tous les étiquetages de , le produit est pris sur tous les bords pour un graphique et est une fonction arbitraire....
Sous une forme simple: Un automate fini bidirectionnel peut-il reconnaître des graphes en vertex contenant un triangle avec des états ?vvvo ( v3)o(v3)o(v^3) Détails D' un intérêt ici sont graphiques de -vertex codées en utilisant une séquence de bords, chaque bord étant une paire de sommets...
J'essaie de comprendre certains concepts sur la décomposition modulaire et les graphiques à largeur de clique . Dans cet article ("On P4-tidy graphs"), il y a une preuve de la façon de résoudre des problèmes d'optimisation comme le nombre de cliques ou le nombre chromatique en utilisant la...
Le problème du kkk cycle est le suivant: Instance: Un graphe non orienté GGGavec nnn sommets et jusqu'à arêtes.(n2)(n2)n \choose 2 Question: Existe-t-il un (bon) kkk cycle dans GGG ? Contexte: Pour tout k fixe kkk, nous pouvons résoudre un cycle de 2k2k2k en temps O(n2)O(n2)O(n^2) . Raphael Yuster,...
Quels sont les bons papiers / livres pour mieux comprendre le pouvoir de la décomposition modulaire et ses propriétés? Je m'intéresse particulièrement aux aspects algorithmiques de la décomposition modulaire. J'ai entendu dire qu'il est possible de trouver une décomposition modulaire d'un graphe en...
L'algorithme hongrois est un algorithme d'optimisation combinatoire qui résout le problème d'appariement bipartite de poids maximum en temps polynomial et a anticipé le développement ultérieur de l'importante méthode primal-dual . L'algorithme a été développé et publié par Harold Kuhn en 1955, qui...
J'implémente un système dont une partie nécessite de l'aide. Je le conçois donc comme un problème de graphe pour le rendre indépendant du domaine. Problème: On nous donne un graphe acyclique dirigé . Sans perte de généralité, supposons que G a exactement un sommet source s et exactement un sommet...
Nous savons que l'algorithme de raccourci de Karger peut être utilisé pour prouver (de manière non constructive) que le nombre maximal de raccourcis possibles qu'un graphique peut avoir est .(n2)(n2)n \choose 2 Je me demandais si nous pouvions en quelque sorte prouver cette identité en donnant une...
La propagation de la croyance s'est avérée être une méthode très puissante grâce à la recherche de modèles graphiques probabilistes. Cependant, je ne connais rien de BP comparable aux méthodes MCMC où nous pouvons avoir des schémas d'approximation randomisés entièrement polynomiaux (FPRAS) pour les...
Le problème de chemin le plus long est NP-difficile. La preuve (typique?) Repose sur une réduction du problème du chemin hamiltonien (qui est NP-complet). Notez qu'ici, le chemin est considéré comme (nœud-) simple. Autrement dit, aucun sommet ne peut apparaître plus d'une fois dans le chemin....
Etant donné un graphe, , je veux trouver un optimal r -domination pour G . C'est, je veux un sous - ensemble S de V tel que tous les sommets de G sont à une distance d'au plus r de un sommet en S , tout en minimisant la taille S .G=(V,E)G=(V,E)G = (V, E)rrrGGGSSSVVVGGGrrrSSSSSS D'après ce que j'ai...
Soit G un graphe non orienté à n nœuds, et soit T un sous-ensemble de nœuds de V (G) appelés terminaux . Un conservateur de distance de (G, T) est un graphe H satisfaisant la propriété réH( u , v ) = dg( u , v )réH(u,v)=rég(u,v)d_H(u,v) = d_G(u,v) pour tous les nœuds u, v dans T. (Notez que H n'est...
Quelle est la complexité du problème suivant? Entrée : unchemin hamiltonienen K nHHHKnKnK_n un sous-ensemble de paires de sommetsR⊆[n]2R⊆[n]2R \subseteq [n]^2 un entier positif kkk Requête : existe-t-il un correspondant tel que pour chaque , ? (où G = ( [ n ] , M ∪ H ) )MMM(v,u)∈R(v,u)∈R(v,u) \in...
Étant donné un graphique cyclique dirigé où le poids de chaque bord peut être négatif, le concept de "chemin le plus court" n'a de sens que s'il n'y a pas de cycles négatifs, et dans ce cas, vous pouvez appliquer l'algorithme Bellman-Ford. Cependant, je suis intéressé à trouver le chemin le plus...