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
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...
Que faire si l'on sait quelque chose sur la complexité paramétrée du calcul du nombre d'intersection d'un graphe (le plus petit nombre de cliques nécessaires pour couvrir tous ses bords)? Il est connu depuis longtemps pour être NP-complet, et c'est évidemment FPT car il a un noyau: si vous pouvez...
Pour un graphe orienté acyclique , est - il une structure de données qui permet des requêtes sans nécessiter joignabilité espace quadratique ou le temps linéaire? Idéalement, je recherche un algorithme utilisant uniquement l'espace O (log n) par sommet et le temps logarithmique⟨ V,...
Étant donné un graphe acyclique dirigé, , est-il possible de supporter efficacement les opérations suivantes?G(V,E)g(V,E)G(V,E) : détermine s'il existe un chemin dans G du noeud a au noeud bisCo n n ected(G,a,b)jesConnecteré(g,une,b)isConnected(G,a,b)GgGauneabbb : Ajoute une arête de a à b dans le...
Disons qu'un graphe est ( a , b ) -connexe si la suppression de tout un des sommets et des b arêtes de G feuilles toujours un graphe connexe. Par exemple, un graphe connecté k , selon la définition standard, est connecté ( k - 1 , 0 ) , selon la nouvelle définition. Existe-t-il un algorithme...
On m'a dit qu'il existe de bons algorithmes de temps polynomiaux pour approximer le nombre de chemins simples dans un graphe orienté d'un sommet de départ donné à un sommet de fin donné t . Quelqu'un connaît-il une bonne référence à ce sujet?sssttt Contexte: compter le nombre exact de chemins dans...
Un réseau de commutation (le nom est inventé) est constitué de trois types de nœuds: un nœud de démarrage un nœud d'extrémité un ou plusieurs nœuds Switch Le nœud de commutation a 3 sorties: Gauche, Haut, Droite; a deux états L et R et un état cible TL ou TR . Chaque commutateur peut être traversé...
Nous savons que nous pouvons représenter n'importe quel graphe planaire par un ensemble de cercles dans le plan, connu sous le nom de graphe de pièces . Chaque cercle représente un sommet et il y a un bord entre deux sommets si et seulement si les cercles "s'embrassent" à leur frontière. Supposons...
Comme on le sait, une décomposition arborescente d'un graphe est constituée d'un arbre avec un sac associé pour chaque sommet , ce qui satisfait les conditions suivantes:T T v ⊆ V ( G ) v ∈ V ( T )GGGTTTTv⊆V(G)Tv⊆V(G)T_v \subseteq V(G)v∈V(T)v∈V(T)v \in V(T) Chaque sommet du se produit dans un...
Quel est le meilleur résultat déterministe pour maintenir la fermeture transitive dynamique dans un graphique dirigé avec seulement une insertion de bord? J'ai lu quelques articles sur le problème de fermeture transitive dynamique avec l'insertion et la suppression de bord. Cependant, existe-t-il...
J'essaie de comprendre comment fonctionne le graphique de chemin selon l'algorithme d'Eppstein dans cet article et comment je peux reconstruire les k chemins les plus courts de s à t avec la construction de tas correspondante H ( G )P(G)P(G)P(G)kkkssstttH(G)H(G)H(G) . Jusque là: contient...
Étant donné un graphe non dirigé à nnn sommets, quelle est la limite d'exécution la plus connue pour trouver un sous-graphe qui est un k×kk×kk\times k -biclique? Existe-t-il des algorithmes paramétrés plus rapides que l'algorithme de temps consiste à "deviner" un côté de la biclique et à voir s'il...
Je ne travaille pas en théorie, mais mon travail nécessite de lire (et de comprendre) des articles théoriques de temps en temps. Une fois que j'ai compris un (ensemble de) résultats, je discute de ces résultats avec des gens avec qui je travaille, dont la plupart ne fonctionnent pas aussi en...
Nous savons que des colorants bord de un graphe sont des colorants sommets d'un graphe spécial, à savoir du graphique de la ligne de .GGG GL(G)L(G)L(G)GGG Existe-t-il un opérateur de graphe tel que les colorations des sommets d'un graphe sont des colorations de bord du graphe ? Je m'intéresse à un...
Un couvercle de bord est un sous-ensemble de bords d'un graphique de sorte que chaque sommet du graphique est adjacent à au moins un bord du couvercle. Les deux articles suivants indiquent que le comptage des couvertures de bord est # P-complet: Un FPTAS simple pour compter les couvertures de bord...
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...
Tout graphique planaire , respectivement, externe satisfait | E ′ | ≤ 3 | V ′ | - 6 , respectivement, | E ′ | ≤ 2 | V ′ | - 3 , pour chaque sous-graphe G ′ = ( V ′ , E ′ ) de GG=(V,E)G=(V,E)G=(V,E)|E′|≤3|V′|−6|E′|≤3|V′|−6|E'|\le 3|V'|-6|E′|≤2|V′|−3|E′|≤2|V′|−3|E'|\le...
Soit ensembles qui peuvent avoir des éléments en commun. Je cherche un plus petit ensemble X tel que ∀ i ,S1, S2, … ,SnS1,S2,…,SnS_1,S_2,\ldots,S_nXXX .∀ i ,X∩ Sje≠ ∅∀je,X∩Sje≠∅\forall i,\,X\cap S_i \ne \emptyset Ce problème a-t-il un nom? Ou cela se réduit-il à un problème connu? Dans mon contexte...