Cette question est liée à l'une de mes questions précédentes, les problèmes NP-difficiles sur les arbres . Je recherche des problèmes P-complets sur les arbres.
Dans leur article Approximate Distance Oracles , Thorup et Zwick ont montré que pour tout graphique non orienté pondéré, il est possible de construire une structure de données de taille qui peut renvoyer une ( 2 k - 1 ) approximative distance entre n'importe quelle paire de sommets dans le...
GI et Knot Problem sont tous deux des problèmes de décision d'équivalence structurelle d'objets mathématiques. Y a-t-il des résultats établissant des liens entre eux? De jolies connexions du problème des nœuds à la physique statistique ont été explorées via des polynômes de nœuds , y a-t-il des...
Je me demande comment trouver la circonférence d'un graphe non orienté clairsemé. Par clairsemé, je veux dire . Par optimal, j'entends la complexité temporelle la plus faible.|E|=O(|V|)|E|=O(|V|)|E|=O(|V|) J'ai pensé à une modification de l'algorithme de Tarjan pour les graphiques non orientés,...
Les graphes de Paley P q sont ceux dont l'ensemble des sommets est donné par le champ fini GF (q), pour les puissances premières q≡1 (mod 4), et où deux sommets sont adjacents si et seulement s'ils diffèrent de 2 pour certains a ∈ GF (q). Dans le cas où q est premier, le champ fini GF (q) n'est que...
Ceci est une question inspirée par le problème de la coupe H sans . Étant donné un graphe, une partition de son ensemble de sommets en r parties V 1 , V 2 , … , V r est sans H si G [ V i ] n'induit pas une copie de H pour tout i , 1 ≤ i ≤ rVVVrrrV1,V2,…,VrV1,V2,…,VrV_1, V_2, \ldots,...
Je suis intéressé à comprendre la structure de la classe des graphes telle sorte qu'il n'y ait pas de sous-graphe induit par un sommet sur quatre sommets qui soit une correspondance parfaite. Autrement dit pour quatre sommets a , b , c , d dans G si a b et c d sont des arêtes, le graphique doit...
Comme le titre l'indique, quelle est la définition correcte de arbre? Il existe plusieurs articles qui parlent d' arbres et d' arbres partiels comme définitions alternatives pour les graphiques avec une largeur d'arbre bornée, et j'ai vu de nombreuses définitions apparemment incorrectes. Par...
Pour quels graphiques non orientés tous les arbres de recherche en profondeur d'abord (pour tous les sommets de départ possibles et pour tous les choix des voisins à rechercher en premier) sont-ils des chemins dirigés? C'est-à-dire que chaque arbre DFS ne doit avoir qu'une seule feuille et que...
Supposons que nous ayons un ensemble S de graphes (graphes finis, mais un nombre infini d'entre eux) et un groupe P de permutations qui agit sur S. Instance: Une permutation p dans P. Question: Existe-t-il un graphe g dans S qui admette l'automorphisme p? Ce problème est-il NP-complet pour certains...
Soit une classe de graphiques avec une largeur de clique bornée. Dans chaque graphique en G, certaines arêtes sont contractées (par exemple au hasard). La largeur de la clique est-elle toujours limitée?ggGggG Dans le cas où il n'est (en général) plus délimité, je serais très intéressé par un...
Dans le problème d'extensibilité, on nous donne une partie de la solution et nous voulons décider si nous pouvons l'étendre à une solution complète. Certains problèmes d'extensibilité peuvent être résolus efficacement tandis que d'autres problèmes d'extensibilité transforment un problème facile en...
J'ai essayé la relaxation LP suivante de l'ensemble indépendant maximum max∑iximax∑ixi\max \sum_i x_i s.t. xi+xj≤1 ∀(i,j)∈Es.t. xi+xj≤1 ∀(i,j)∈E\text{s.t.}\ x_i+x_j\le 1\ \forall (i,j)\in E xi≥0xi≥0x_i\ge 0 J'obtiens 1/21/21/2 pour chaque variable pour chaque graphique non bipartite cubique que...
dans le Bundeswettberweb Infomatik 2010/2011, il y avait un problème intéressant: Pour fixe , trouver un k minimal et une carte φ : { ( i , j ) | i ≤ j ≤ n } → { 1 , … , k } , de sorte qu'il n'y a pas de triple ( i , j ) , ( i + l , j ) , ( i + l , j + l ) avec φ ( innnkkkφ : { ( i , j ) | i ≤ j ≤...
Contexte Cette question est motivée par un jeu de société appelé «Dracula». Dans ce jeu, il y a un vampire et quatre chasseurs, le but des chasseurs est d'attraper le vampire. Le jeu se déroule en Europe. Le jeu se présente comme suit: 1. Le joueur chasseur place tous les chasseurs dans les villes....
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)...
Chong, Han et Lam ont montré que la connectivité st non dirigée peut être résolue sur la PRRE EREW en temps avec des processeurs O ( m + n ) .O ( log n )O(Journaln)O({\log}n)O ( m + n )O(m+n)O(m+n) Quel est l'algorithme parallèle le plus connu pour la connectivité st dans les graphes planaires...
Dans cet article de Kempe-Kleinberg-Tardos, les auteurs proposent des algorithmes gourmands basés sur des fonctions sous-modulaires pour déterminer les nœuds les plus influents d'un graphe, avec des applications aux réseaux sociaux.kkk Fondamentalement, l'algorithme se présente comme suit: S= e m p...
Étant donné un graphe planaire, on peut l'intégrer dans un temps linéaire traversant librement dans une grille . Je voudrais savoir si des algorithmes efficaces sont connus pour incorporer en ligne droite un graphe plan passant librement dans une grille n c × n c , pour certains petits c , de sorte...
Supposons qu'il existe un graphique . Je veux tester si peut être partitionné en deux ensembles disjoints et telle sorte que les sous-graphes induits par et sont des graphiques d'intervalle d'unité.G = ( V, E)g=(V,E)G=(V,E)VVVV1V1V_1V2V2V_2V1V1V_1V2V2V_2 Je connais la complétude NP de la...