L'article "Algorithmes sous-quadratiques pour 3SUM", par Ilya Baran, Erik D. Demaine, Mihai Patrascu a la complexité suivante pour le Problème 3SUM: étant donné une liste LLL de nnn entiers s'il y a x,y,z∈Lx,y,z∈Lx,y,z \in L tels que x+y=z.x+y=z.x+y=z. w−w−w-A C 0 O ( n 2 / w 2 log w ) O ( n 2 / (...
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...
Je lis sur les classes de graphiques pour lesquels Graphique Isomorphisme ( ) est en . Un de ces cas est des graphiques de valence bornée (maximum sur le degré de chaque sommet) comme expliqué ici . Mais je l'ai trouvé trop abstrait. Je serais reconnaissant si quelqu'un pouvait me suggérer quelques...
É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...
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...
Quelles sont les méthodes les plus connues pour la convolution cyclique de longueur nnn sur un petit champ, c'est-à-dire quand |F|≪n|F|≪n|\mathbb{F}| \ll n ? Je suis particulièrement intéressé par les champs de taille constante, ou même . Les déclarations et références générales sur l'efficacité...
Les graphes planaires ont le genre zéro. Les graphiques embarquables sur un tore ont un genre au maximum 1. Ma question est simple: Y a-t-il des problèmes qui peuvent être résolus polynomialement sur les graphes planaires mais NP-dur sur les graphes du genre un? Plus généralement, y a-t-il des...
Dans l'algorithme de Strassen, pour calculer le produit de deux matrices et , les matrices et sont divisées en matrices de blocs et l'algorithme procède calcul récursif de produits matrice-matrice à blocs par opposition à un produit matriciel matriciel à blocs, c'est-à-dire si nous voulons , où B A...
Considérez ce problème: étant donné une liste d'ensembles finis, recherchez un ordre qui minimise .s1,s2,s3,…s1,s2,s3,…s_1, s_2, s_3, \ldots|s1|+|s1∪s2|+|s1∪s2∪s3|+…|s1|+|s1∪s2|+|s1∪s2∪s3|+…|s_1| + |s_1 \cup s_2| + |s_1 \cup s_2 \cup s_3| + \ldots Existe-t-il des algorithmes connus pour cela?...
J'ai deux partitions de et je recherche la distance d'édition entre elles.[1…n][1…n][1 \ldots n] Par cela, je veux trouver le nombre minimal de transitions uniques d'un nœud dans un groupe différent qui sont nécessaires pour passer de la partition A à la partition B. Par exemple, la distance de {0...
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...
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...
En lisant le blog de Dick Lipton, je suis tombé sur le fait suivant vers la fin de son billet Bourne Factor : Si, pour tout , il existe une relation de la forme où , et chacun des , et ont une longueur de bits , puis l'affacturage a un polynôme circuits de
Comme dans, le domaine des articles dans le ACM Journal on Experimental Algorithmic JEA . Quels ont été les travaux fondateurs? Quels sont les principaux résultats? Comment sont-ils caractérisés? Des liens intéressants avec d'autres domaines de
Contexte Un arbre de décision binaire TTT est un arbre enraciné où chaque nœud interne (et racine) est étiqueté par un index sorte qu'aucun chemin de la racine à la feuille ne répète un index, les feuilles sont étiquetés par des sorties dans , et chaque bord est étiqueté par pour l'enfant gauche et...
Supposons que l'on nous donne une matrice n par n, M, avec des entrées entières. Peut-on décider dans P s'il existe une permutation telle que pour toutes les permutations π ≠ σ on a Π M i σ ( i ) ≠ Π M i π ( i ) ?σσ\sigmaπ≠ σπ≠σ\pi\ne\sigmaΠ Mi σ( i )≠ Π Mi π( i )ΠMjeσ(je)≠ΠMjeπ(je)\Pi...
On nous donne une famille FF\mathcal{F} de mmm sous-ensembles de {1, ..., n}. Est-il possible de trouver une borne inférieure non triviale sur la complexité de décider si FF\mathcal{F} est une famille Sperner? La borne inférieure triviale est O(nm)O(nm)O(n m) et je soupçonne fortement qu'elle n'est...
Étant donné les points dans R d et une distance l, trouver le plus grand sous-ensemble de ces points de sorte que la distance euclidienne de deux d'entre eux ne dépasse pas l .p1,…,pnp1,…,pnp_1,\ldots,p_nRdRd\mathbb{R}^{d}llllll Quelle est la complexité de ce problème? Dans le graphique sur les...
Une question récente a discuté de l'algorithme de programmation dynamique désormais classique pour TSP, dû indépendamment à Bellman et Held-Karp . Il est universellement rapporté que l' algorithme s'exécute en temps . Cependant, comme l'un de mes étudiants l'a récemment souligné, ce temps...
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...