Questions marquées «ds.algorithms»

Étant donné un plan fini, j'ai une tessellation hexagonale de ce plan avec un hexagone régulier de taille fixe. Je calcule ensuite le graphe de Delaunay G pour la pavage. Étant donné un tel graphique G, je supprime des ensembles spécifiques de nœuds dans ce graphique pour produire plusieurs...

Je parcourais le papier séminal de Les Valiant et j'ai eu du mal avec la proposition 4.3 à la page 10 du papier. Je ne vois pas pourquoi est-ce que s'il y a un générateur avec certaines valeurs pour avec une base , alors il existe un générateur avec les mêmes valeurs pour tout base ( ) ou ( ) pour...

Je m'intéresse aux exemples explicites de graphiques pour lesquels l'application des algorithmes de Goemans et Williamson pour approximer les coupes maximales donne un facteur d'approximation de 0,878…. L'algorithme pour créer de telles instances serait parfait, les exemples explicites et les...

Greedy est un terme non formel, mais il pourrait être (je ne suis pas sûr, c'est pourquoi je demande) que pour certains problèmes, la cupidité peut être formulée mathématiquement et ainsi être prouvée qu'aucun algorithme gourmand optimal n'existe. Est-ce

Il y a eu pas mal de travail sur les problèmes de calcul pour les commandes partielles (par exemple, la reconnaissance, le nombre de sauts, la reconnaissance du graphe de comparabilité, etc.). Je suis curieux de savoir quel travail spécifique aux réseaux a été fait. J'ai cherché autour et je n'ai...

REMARQUE : La question a été reformulée dans mes réponses: en supposant maintenant que nous pouvons trouver les ancêtres frères les plus bas en , l'ANN peut-il vraiment être exécuté en ?O ( log n )O ( 1 )O(1)O(1)O ( logn )O(log⁡n)O(\log n) Les Quadtrees sont des indices spatiaux efficaces. J'ai un...

Disons que nous avons un polyèdre sous forme standard: Ax=bx≥0Ax=bx≥0\begin{equation*} \begin{array}{rl} \mathbf{A}\mathbf{x} = \mathbf{b} \\\\ \mathbf{x} \ge 0 \end{array} \end{equation*} Existe-t-il des méthodes connues pour trouver un hyperplan qui divise le polyèdre de manière à ce que le...

Existe-t-il un algorithme polynomial pour trouver, s'il en existe un, une araignée s'étendant sur un graphe donné ? Une araignée est un arbre avec au plus un nœud avec un degré supérieur à 2: je sais que diverses conditions de degré sur G (essentiellement, des degrés de nœud suffisamment grands)...

J'ai 400 balles, dont 100 rouges, 40 jaunes, 50 vertes, 60 bleues, 70 violettes, 80 noires. (les boules de la même couleur sont identiques) j'ai besoin d'un algorithme de brassage efficace, de sorte qu'après le brassage, les balles soient dans une liste, et Les 3 balles consécutives ne sont pas de...

Je voudrais savoir si le problème simple suivant a déjà été étudié et si une solution est connue. Soit G une grille finie (MxN), S un sous-ensemble de cellules de G (les "miettes"). On dit que deux miettes sont connectées (localement) si leurs coordonnées diffèrent d'au plus une (c'est-à-dire que...

Étant donné un graphe planaire non pondéré et une collection de paires de sommets ( k ≥ 2 est une constante), trouver k chemins vertex-disjoints (sauf source) de s à t i tel que la longueur du chemin le plus long soit

Supposons que nous considérons 3-SAT avec des variables et des clauses . Je recherche une méthode qui semble prendre temps / espace pour résoudre tout problème SAT correspondant à cette description, à l'intérieur d'une erreur qui peut être ajustée à un montant arbitraire. Cependant, il y a un hic.c...

Pour un graphe non orienté et un ensemble de sommets, ce qui est l'algorithme connu asymptotiquement le plus rapide pour trouver un chemin simple contenant tous les éléments de . Et si nous voulons que le chemin soit le plus court possible?S

Dans l'étude sur deux problèmes de théorie de l'information , Erdõs et Rényi donnent des limites inférieures sur le nombre minimum de pesées à faire pour déterminer le nombre de fausses pièces dans un ensemble de pièces.nnn Plus formellement: Les fausses pièces ont un poids plus petit que les...

Soit un graphe non orienté. Une décomposition de en sous-ensembles disjoints est appelée une décomposition de Hamilton de si le sous-graphe induit par chaque ensemble est soit un graphe de Hamilton, soit un seul bord avec .V V iG = ( V, E)g=(V,E)G=(V,E)VVVVjeVjeV_iV i | V i | = 2ggGVjeVjeV_i| Vje|...

J'essaie d'utiliser des arbres de suffixes pour comparer les séquences de chaînes. J'ai trouvé des implémentations / théorie pour le problème de sous-chaîne commun le plus long en utilisant des arbres de suffixes. Cependant, ce que je recherche est une discussion du problème connexe - "toutes les...

Je sais que pour un graphique bipartite non pondéré, je peux trouver la couverture de sommet minimale en trouvant d'abord la correspondance maximale et en la transformant en couverture de sommet en utilisant le théorème de König. Y a-t-il une modification que l'on pourrait utiliser si les nœuds...

Les représentations les plus simples pour les graphiques utilisent des matrices / listes d'adjacence, ce qui signifie que chaque nœud et bord est explicitement représenté. L'importance des représentations implicites pour les graphiques présentant de fortes régularités est reconnue depuis longtemps....

Soit . J'ai besoin de générer de simples graphiques G de circonférence g de telle sorte que l'ensemble de tous les g- cycles forme une couverture de double bord de G (c'est-à-dire que chaque bord est partagé par exactement deux g- cycles), et de telle sorte que l'intersection de deux g -cycles est...

Il semble y avoir de nombreux algorithmes randomisés pour les tests d'identité polynomiale, vérifiant si un polynôme donné est nul ou non. Y a-t-il des résultats d'algorithmes qui font une sorte d'estimation des polynômes sur un ensemble spécifique de points? Cela pourrait être, par exemple, une...