48 artículos
Este artículo presenta una demostración breve y autocontenida del teorema de Delahan, que establece que todo grafo simple de vértices aparece como subgrafo inducido en un grafo de Steinhaus con vértices, utilizando para ello el concepto de conjuntos de índices generadores para triángulos de Steinhaus.
Este artículo caracteriza la resolubilidad de los acertijos de coincidencia de permutaciones mediante la aciclicidad de un grafo de restricciones, proporciona una fórmula de longitud de gancho para contar las soluciones, ofrece un algoritmo lineal para reparar puzzles no resolubles y demuestra que la generalización con permutaciones arbitrarias es NP-completa.
Este artículo estudia la propiedad WELLDOC (ocurrencias bien distribuidas) en palabras infinitas y establece un criterio para determinar su validez en palabras generadas por morfismos.
Este trabajo proporciona una caracterización completa de los digrafos de anidamiento de intervalos mediante ordenamientos lineales de vértices con patrones prohibidos, denominados ordenamientos de anidamiento, completando así el panorama de las caracterizaciones por ordenamientos para las principales subclases de digrafos de intervalos.
Este artículo presenta una versión completa y optimizada del algoritmo de Eden, Ron y Seshadhri para aproximar el grado promedio de grafos con arboricidad acotada, eliminando factores logarítmicos innecesarios y logrando una complejidad de consultas de .
El artículo presenta una versión del teorema del árbol matricial que relaciona el determinante de una matriz con sumas de pesos de arborescencias en grafos dirigidos, extendiendo el resultado a matrices con sumas de columnas no nulas mediante la adición de un vértice raíz, y lo aplica para demostrar un teorema de todos los menores, calcular la evolución temporal de sistemas de estados discretos y proponer estrategias para el cálculo de determinantes.
Este artículo desarrolla herramientas para el estudio cuantitativo de los árboles de expansión mínimos aleatorios (MST), analizando tanto el caso estándar con pesos independientes e idénticamente distribuidos como generalizaciones hacia medidas producto con distribuciones arbitrarias.
Este artículo investiga las propiedades del número cromático lineal y establece límites mejorados en varias clases de grafos, abordando la conjetura de que la profundidad del árbol está acotada superiormente por el doble de dicho parámetro.
Este artículo proporciona la justificación teórica de que el marco -DRESS distingue pares CFI para todo y demuestra condicionalmente que su poder de discriminación es al menos equivalente al de la jerarquía -WL para todos los grafos.
Este artículo establece un umbral de probabilidad para que una colección aleatoria de subconjuntos defina un matroide binomial, demuestra que tales estructuras son casi seguramente matroides pavimentados dispersos, y mejora las estimaciones asintóticas del número de matroides permitiendo que el rango crezca lentamente con el tamaño del conjunto base.
Este artículo determina la estructura completa de los valores nim en juegos de sustracción aditivos del régimen cuadrático primitivo, proporcionando una demostración rigurosa de una fórmula cerrada conocida desde 1982 y estableciendo que cada secuencia de valores nim reside en un desplazamiento lineal de las posiciones P clásicas.
Este artículo desarrolla fórmulas explícitas y compactas para el polinomio M de varios productos de grafos (como el cartesiano, directo, fuerte, lexicográfico, de diferencia simétrica, disyunción y de Sierpiński), proporcionando una descripción unificada de cómo interactúan los grados de los vértices en estas construcciones y extendiendo así los resultados existentes para índices topológicos basados en grados.
Este artículo propone dos métodos cuantitativos basados en valores de referencia para calcular vectores de peso a partir de matrices incompletas de comparaciones por pares, demostrando la optimalidad y existencia de soluciones para sus variantes geométrica y aritmética.
Este artículo presenta un algoritmo de tiempo fijo parametrizado (FPT) que extiende el teorema de Gallai-Milgram al demostrar que es posible decidir en tiempo polinómico si un grafo puede cubrirse con menos caminos que su número de independencia, resolviendo así una cuestión abierta y proporcionando la primera solución para problemas como la Hamiltonicidad en grafos con número de independencia pequeño.
Este artículo introduce y estudia las sobredistribuciones separadas por bloques, demostrando que su estructura combinatoria está gobernada por números de Fibonacci, lo que permite obtener representaciones algebraicas y recursivas de su función generadora, así como determinar su crecimiento asintótico, el cual comparte la misma escala exponencial que las particiones ordinarias.
Este artículo demuestra una versión más débil de una conjetura reciente sobre la descomposición arbórea de grafos que excluyen ciertos menores inducidos, estableciendo que tales grafos admiten una descomposición donde la independencia a cierta distancia de cada bolsa está acotada por una función polilogarítmica.
Este artículo presenta una generalización unificada de la operación de conmutación para (n,m)-grafos, establece resultados fundamentales sobre sus homomorfismos, resuelve problemas abiertos mediante la construcción de un producto categórico y determina el número cromático para bosques utilizando nociones de teoría de grupos.
Este artículo establece una dicotomía de complejidad para el problema de reconfiguración de conjuntos dominantes a distancia , demostrando que es resoluble en tiempo polinómico en grafos divididos para y diseñando un algoritmo lineal en árboles, mientras que se mantiene como completo para PSPACE en grafos planares de grado máximo tres y en grafos bipartitos o cordales.
Este artículo estudia la complejidad parametrizada del problema del camino más corto con restricciones disyuntivas positivas, estableciendo la NP-completitud de su versión clásica y presentando resultados de kernelización y tractabilidad parametrizada fija para diferentes parámetros estructurales y de tamaño de solución.
Este trabajo demuestra que los algoritmos cuánticos de sistemas lineales pueden resolver ecuaciones de Poisson 3D heterogéneas aplicadas al flujo de fracturas geológicas con una ventaja de tiempo y memoria sobre los métodos clásicos, aunque revela que la codificación en bloques de precondicionadores por separado no mejora el número de condición efectivo, lo que subraya la necesidad de reducir este parámetro para lograr ventajas cuánticas prácticas.