Considérez le problème suivant. Entrée: Un graphique non orienté . Sortie: Un graphique H qui est un mineur de G avec la densité de bord la plus élevée parmi tous les mineurs de G , c'est-à-dire avec le rapport le plus élevé | E ( H ) | / | V ( H ) |
La preuve d'Omer Reingold que donne un algorithme pour USTCON (dans un graphe orienté U avec des sommets spéciaux s et t , sont-ils ConL=SLL=SLL=SLsssttt CONNECTE?) En utilisant uniquement logspace. L'idée de base est de construire un graphe d'extension à partir du graphe d'origine, puis de faire...
Je recherche une implémentation d'un algorithme pour calculer la largeur de chemin d'un graphe. Il est bien connu que le calcul de la largeur de trajet équivaut au calcul du nombre de recherche de nœuds, du nombre de séparation de sommets ou de l'épaisseur d'intervalle du graphique. L'algorithme...
Le chapitre 1 du livre The Probabilistic Method, par Alon et Spencer mentionne le problème suivant: Étant donné un graphique , décidez si sa connectivité de bord est au moins ou non.ggGn / 2n/2n/2 L'auteur mentionne l'existence d'un algorithme par Matula et l'améliore à .O ( n3)O(n3)O(n^3)O (...
Je m'intéresse à la complexité du problème des ensembles dominants (DSP) dans certaines classes de graphes spécifiques qui sont des sous-classes de graphes d' accord . Un graphe est un graphe de chemin non orienté s'il s'agit du graphe d'intersection de sommets d'une famille de chemins dans un...
Un de mes amis me pose le problème de planification suivant sur l'arbre. Je trouve que c'est très propre et intéressant. Y a-t-il une référence pour cela? Problème: Il y a un arbre , chaque arête a un coût de déplacement symétrique de 1 . Pour chaque sommet v i , il existe une tâche qui doit être...
Est-il connu si le problème posé par le sommet de rétroaction sur les graphes planaires non orientés de degré borné est
É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...
On nous donne un graphe acyclique dirigé G = ( V, E)g=(V,E)G=(V,E) avec un nombre associé à chaque sommet ( ), et un nombre cible .g: V→ Ng:V→Ng:V\to \mathbb{N}T∈ NT∈NT\in \mathbb{N} Le problème de somme de sous-ensemble DAG (peut exister sous un nom différent, une référence sera excellente)...
La largeur d'arbre et la largeur de chemin sont des paramètres populaires, mesurant la proximité d'un graphique avec un arbre ou un chemin, respectivement. En effet, il semble que la largeur d'arbre soit si populaire qu'elle figure dans de nombreux articles, livres et notes de cours qui donnent...
La décomposition des arbres est difficile dans le pire des cas, mais la méthode gourmande semble être presque optimale sur les petits réseaux réels. Sait-on quelque chose sur la dureté de la décomposition des arbres d'une instance "typique" d'une classe de graphes? Existe-t-il un exemple de famille...
Cette question est similaire aux problèmes NP-difficiles sur les arbres : Il existe un grand nombre de problèmes NP-complets qui sont traitables sur les cographies . Y a-t-il des problèmes connus qui restent NP-complets lorsqu'ils sont limités aux cographies? Pour être plus précis, je suis...
Je suis à la recherche d'une bonne référence pour les plus courts chemins de goulot d'étranglement. Plus précisément, étant donné les sommets s et t dans un graphique non orienté avec des poids de bord, vous voulez le chemin le plus court de s à t, où la longueur d'un chemin est le bord maximum sur...
Soit points dans le plan R 2 . Considérons un graphique complet avec les points comme sommets et avec des poids de bord de ‖ x i - x j ‖ 2 . Pouvez-vous toujours trouver une réduction de poids d'au moins 2x1,…,xnx1,…,xnx_1, \ldots, x_nR2R2\mathbb{R}^2∥xi−xj∥2‖xi−xj‖2\|x_i - x_j\|^2 du poids total?...
Une propriété de graphe est appelée héréditaire si elle se ferme par rapport à la suppression de sommets (c'est-à-dire que tous les sous-graphes induits héritent de la propriété). Une propriété de graphe est appelée additive si elle est fermée par rapport à la prise d'unions disjointes. Il n'est...
Dans mon travail, le problème suivant se pose: Existe-t-il un algorithme connu, qui se rapproche du nombre chromatique d'un graphique sans un ensemble indépendant d'ordre 65? (Donc alpha (G) <= 64 est connu et | V | / 64 est une borne inférieure triviale, | V | une borne supérieure triviale....
Étant donné un graphe , nous devons trouver la cardinalité du plus grand ensemble de sommets afin que chacun d'eux soit présent dans chaque correspondance maximale possible.gGG Existe-t-il une solution à côté de l'évidence, supprimez chaque sommet et trouvez la correspondance maximale pour la voir...
Il y a eu quelques efforts pour attaquer le problème d'isomorphisme des graphes en utilisant la marche aléatoire quantique des bosons à noyau dur (symétrique mais sans double occupation). La puissance symétrique de la matrice d'adjacence, qui semblait prometteuse, s'est révélée incomplète pour les...
Dans le célèbre contre-exemple de l'isomorphisme des graphes via la méthode de Weisfeiler-Lehman (WL), le gadget suivant a été construit dans cet article par Cai, Furer et Immerman. Ils construisent un graphe donné parXk= ( Vk, Ek)Xk=(Vk,Ek)X_k = (V_k, E_k) Vk= Ak∪ Bk∪ Mk où UNEk= { aje∣ 1 ≤ i ≤ k...
Je cherche un petit graphe GGG dont le nombre chromatique vectoriel est plus petit que le nombre chromatique,