48 articles
Cet article présente une preuve courte et autonome du théorème de Delahan, démontrant que tout graphe simple à sommets est un sous-graphe induit d'un graphe de Steinhaus à sommets, en utilisant la notion d'ensembles d'indices générateurs pour les triangles de Steinhaus.
Cet article caractérise la résolubilité et le nombre de solutions des puzzles de correspondance de permutations sur grille, fournit un algorithme linéaire pour corriger les instances non résolubles, et démontre que la généralisation du problème à des permutations arbitraires est NP-complète.
Cet article étudie la propriété WELLDOC, une notion de distribution abélienne des occurrences dans les mots infinis, et fournit un critère pour déterminer si les mots générés par des morphismes possèdent cette propriété.
Cet article établit une caractérisation complète des digraphes d'intervalles emboîtés en termes d'ordonnancements linéaires des sommets évitant certains motifs, appelés ordonnancements emboîtés, comblant ainsi une lacune dans la compréhension des sous-classes principales des digraphes d'intervalles.
Cette note présente une version simplifiée et optimisée de l'algorithme d'Eden, Ron et Seshadhri pour approximer le degré moyen d'un graphe d'arboricité bornée, éliminant les facteurs logarithmiques superflus grâce à une analyse complète et une complexité en requêtes de .
Cet article présente une version généralisée du théorème de l'arbre matriciel pour les graphes dirigés avec des sommes de colonnes non nulles, permettant de relier les déterminants et les mineurs d'une matrice à des sommes pondérées d'arborescences et de forêts, avec des applications à l'évolution temporelle des systèmes discrets et au calcul des déterminants.
Cet article développe des outils pour l'étude quantitative des arbres couvrants minimaux (MST) aléatoires, en considérant des poids indépendants tirés d'une distribution unique ou de distributions arbitraires formant des mesures produit.
Cet article étudie les propriétés du nombre chromatique linéaire et établit des bornes améliorées pour cette mesure dans plusieurs classes de graphes, en réponse à une conjecture liant ce paramètre à la profondeur d'arbre.
Cet article établit théoriquement que le cadre -DRESS distingue systématiquement les paires CFI et atteint au moins le niveau de la hiérarchie WL, confirmant ainsi par des preuves inconditionnelles et conditionnelles la puissance discriminante de cette méthode itérative basée sur les sous-graphes.
Cet article établit des seuils de probabilité précis pour qu'un ensemble aléatoire de sous-ensembles forme une base de matroïde, démontre que ces structures sont presque sûrement des matroïdes épars pavants, et améliore les estimations asymptotiques du nombre de matroïdes en permettant au rang de croître avec .
Cet article établit la structure complète des valeurs de Nim pour les jeux de soustraction additifs dans le régime quadratique primitif, en fournissant une preuve rigoureuse d'une formule fermée existante et en démontrant que chaque séquence de valeurs de Nim correspond à un décalage linéaire des positions P classiques.
Cet article développe des formules explicites et compactes pour le polynôme M de sept types de produits de graphes (direct, cartésien, fort, lexicographique, différence symétrique, disjonction et Sierpiński), offrant ainsi une description unifiée de la propagation des interactions de degrés des sommets et étendant les résultats existants sur les indices topologiques basés sur les degrés.
Cet article propose deux méthodes quantitatives étendant les heuristiques arithmétique et géométrique (HRE) pour calculer des vecteurs de poids à partir de matrices de comparaisons par paires incomplètes en utilisant des valeurs de référence, tout en démontrant l'optimalité et l'existence de solutions pour la variante géométrique ainsi que des conditions suffisantes pour la variante arithmétique.
Cet article présente un algorithme FPT résolvant la question de savoir si un graphe peut être couvert par moins de chemins, en établissant une extension algorithmique du théorème de Gallai-Milgram et en fournissant le premier algorithme polynomial pour le problème du chemin hamiltonien dans les graphes dont le nombre d'indépendance est au plus trois.
Cet article introduit et analyse les surpartitions séparées par blocs, une famille contrainte dont la structure combinatoire interne régie par des nombres de Fibonacci permet d'établir des formules de récurrence, des représentations déterminantales et une factorisation d'Euler, tout en démontrant que leur croissance asymptotique partage la même échelle exponentielle que celle des partitions ordinaires.
Les auteurs prouvent une version affaiblie d'une conjecture récente sur les décompositions arborescentes des graphes excluant certains mineurs induits, en démontrant que de tels graphes admettent une décomposition où chaque sac possède un nombre d'indépendance à distance borné par une fonction polylogarithmique.
Cet article généralise l'opération de commutation sur les graphes , résout des problèmes ouverts concernant les homomorphismes et les produits catégoriels, et détermine le nombre chromatique pour les forêts en utilisant des notions de théorie des groupes.
Cet article établit une dichotomie de complexité pour le problème de reconfiguration des ensembles dominants à distance en démontrant qu'il est polynomial sur les graphes split pour (contrairement au cas ), tout en fournissant un algorithme linéaire sur les arbres et en prouvant sa complétude PSPACE sur des graphes planaires et bipartis pour .
Cet article étudie la complexité paramétrée du problème du plus court chemin avec des contraintes disjonctives positives, en établissant des noyaux de taille polynomiale et des résultats de tractabilité paramétrée selon la taille de la solution et les propriétés structurelles du graphe de contraintes.
Cet article démontre la faisabilité de l'encodage par blocs de l'équation de Poisson hétérogène tridimensionnelle pour la simulation des écoulements en réseaux de fractures, montrant que bien que l'encodage séparé de la matrice et du préconditionneur n'améliore pas le nombre de conditionnement effectif, l'algorithme quantique offre une accélération temporelle et des économies de mémoire exponentielles par rapport aux méthodes classiques.