Quelles sont les applications du problème de couverture Vertex dans le monde réel? Quels projets industriels ou de recherche utilisent des logiciels réellement mis en œuvre basés sur des résultats théoriques pour le problème Vertex Cover? En particulier, l'un des résultats théoriques suivants...
Soit un graphe. Pour un sommet , définir pour être le (ouvert) voisinage de dans . Autrement dit, . Définissez deux sommets dans comme des jumeaux si et ont le même ensemble de voisins, c'est-à-dire si .G=(V,E)g=(V,E)G=(V,E)x∈VX∈Vx\in
Contexte: Soit u,vu,vu, v deux sommets d'un graphe non orienté . Un ensemble de sommets est un séparateur si et appartiennent à différents composants connectés de . Si aucun sous-ensemble correct d'un séparateur est un séparateur, alors est un séparateur minimal. Un ensemble de sommets est un...
OK, cela peut sembler une question de devoirs et, dans un sens, ça l'est. En tant que devoir à la maison dans une classe d'algorithmes de premier cycle, j'ai donné le classique suivant: Étant donné un graphe non orienté G=(V,E)G=(V,E)G=(V,E) , donner un algorithme qui trouve une coupe telle que ,...
(transféré de MathOverflow) Salut, Je lisais ce fil: /mathpro/16393/finding-a-cycle-of-fixed-length Je veux trouver un cycle 5 sur un graphique. En fait, ce que je veux vraiment, c'est un cycle impair le plus court d'une longueur d'au moins 5, mais c'est peut-être un peu à côté du point. Pour mes...
Supposons qu'un graphe à n sommets soit présenté comme un flux de m arêtes, mais plusieurs passes sont autorisées sur le flux.gGGnnnmmm Monika Rauch Henzinger, Prabhakar Raghavan et Sridar Rajagopalan ont observé que l' espace est nécessaire pour déterminer s'il existe un chemin entre deux sommets...
Une griffe est un K1,3K1,3K_{1,3} . Un algorithme trivial détectera une griffe en temps O(n4)O(n4)O(n^4) . Cela peut être fait dans O(nω+1)O(nω+1)O(n^{\omega+1}) , où ωω\omega est l'exposant de la multiplication matricielle rapide, comme suit: prendre le sous-graphe induit par N[v]N[v]N[v] pour...
Dans la classe de complexité , il y a des problèmes supposés NE PAS être dans la classe , c'est-à-dire des problèmes avec des algorithmes parallèles déterministes. Le problème du débit maximal en est un exemple. Et il y a des problèmes que l'on croyait être dans , mais aucune preuve n'a encore été...
Le graphe linéaire d'un hypergraphe est le graphe (simple) G ayant des arêtes de H comme sommets avec deux arêtes de H adjacentes à G si elles ont une intersection non vide. Un hypergraphe est un r -hypergraphe si chacune de ses arêtes a au plus r sommets.HHHGGGHHHHHHGGGrrrrrr Quelle est la...
Compte tenu d' une famille ensemble FF\mathcal{F} de sous - ensembles d'un univers UUU . Soit S1,S2∈FS1,S2∈FS_1,S_2 \in \mathcal F et nous voulons répondre est S1⊆S2S1⊆S2S_1 \subseteq S_2 . Je recherche une structure de données qui me permettra d'y répondre rapidement. Mon application est de la...
Je cherche des moyens de maintenir un arbre couvrant relativement équilibré d'un graphique, alors que j'ajoute de nouveaux nœuds / arêtes au graphique. J'ai un graphique non orienté qui commence comme un seul nœud, la "racine". À chaque étape, j'ajoute au graphique soit un nouveau nœud et un bord...
Soit le nombre d'arbres couvrant un graphe à sommets. Il existe un algorithme qui calcule dans les opérations arithmétiques . Cet algorithme consiste à calculer , où Q est le laplacien de G et J est la matrice constituée uniquement de 1 . Pour plus d'informations sur cet algorithme, voir Biggs -...
Feedback Vertex Set est NP-complete pour les graphiques généraux. Il est connu qu'il est NP-complet pour les graphiques bornés de degré 8 en raison d'une réduction de la couverture des sommets. L' article de Wikipédia indique qu'il est résoluble en temps poly pour les graphiques bornés de degré 3...
Le calcul de la constante de Cheeger d'un graphique , également connu sous le nom de constante isopérimétrique (car il s'agit essentiellement d'un rapport surface / volume minimum), est connu pour être NP-complet. Elle est généralement approximative. Je voudrais savoir si des algorithmes...
Supposons que nous ayons un graphique pondéré non orienté (avec des poids non négatifs). Supposons que tous les chemins les plus courts dans G soient uniques. Supposons que nous ayons ces chemins (séquences d'arêtes non pondérées), mais ne connaissons pas lui-même. Pouvons-nous produire un qui...
Soit un graphe non orienté non pondéré avec sommets et arêtes. Est-il possible de prétraiter et de produire une structure de données de taille afin qu'il puisse répondre aux requêtes de la forme "distance entre et " dans le temps O (n)?n m G m ⋅ p o l y l o g ( n ) u vgGGnnnmmmgGGm ⋅ p o l y l o g...
Est-il possible de tester algorithmiquement si un nombre calculable est rationnel ou entier? En d'autres termes, serait-il possible pour une bibliothèque qui implémente des nombres calculables de fournir les fonctions isIntegerou isRational? Je suppose que ce n'est pas possible, et que cela est en...
Je voudrais calculer la largeur d' arbre d'un graphique. Il existe de très bonnes heuristiques pour d'autres problèmes de graphes NP-durs tels que VF2 pour l'isomorphisme de sous-graphe, avec du code disponible en igraph par exemple. Je les ai essayés sur mes graphiques et je trouve qu'ils...
Supposons que soit un arbre à degrés constants dont nous ne connaissons pas la structure. Le problème est de sortir l'arbre en posant des requêtes de la forme: "Le nœud se trouve-t-il sur le chemin du nœud au nœud ?". Supposons que chaque requête puisse recevoir une réponse en temps constant par un...
Je voudrais savoir s'il existe des bibliothèques de graphiques gratuites pour tester si un ensemble spécifique de mineurs existe dans un graphique