52 artículos
El artículo presenta HYGENE, el primer método basado en difusión profunda para la generación de hipergrafos realistas y diversos mediante un enfoque de expansión local progresiva sobre su representación bipartita.
Este artículo introduce un nuevo marco de rigidez para polítopos que preserva longitudes de aristas y planaridad de caras pero permite deformar sus formas, demostrando que los polítopos convexos son genéricamente rígidos en dimensión tres y planteando conjeturas para dimensiones superiores.
Este artículo presenta una demostración más accesible y simplificada, utilizando la terminología actual, de que no existen digrafos funcionales primos, un resultado originalmente establecido por Ralph Seifert en 1971.
El artículo demuestra que un método exacto sencillo resuelve casi todas las instancias clásicas de referencia del problema del viajante con ventanas de tiempo en menos de diez segundos, lo que indica que estas ya no son representativas para evaluar algoritmos ni para diseñar conjuntos de entrenamiento difíciles para aprendizaje automático.
Este artículo presenta la demostración de la Conjetura de Erdős sobre emparejamientos, un problema abierto de larga data en combinatoria extremal, estableciendo el límite superior máximo para la cardinalidad de una familia de subconjuntos de tamaño que no contiene subconjuntos disjuntos.
El artículo demuestra que asintóticamente casi todas las funciones vectoriales sobre campos finitos poseen estabilizadores triviales bajo la equivalencia afín extendida, lo que implica que el número de clases de equivalencia coincide con la estimación ingenua y que la probabilidad de que dos funciones aleatorias sean equivalentes es superexponencialmente pequeña, validando así el uso de muestreo aleatorio en el diseño de primitivas criptográficas.
Este trabajo presenta un enfoque de generación de columnas para resolver el problema de flujo multi-commodity con función objetivo convexa, ofreciendo métodos eficientes para sus variantes dividibles e indivisibles en redes de telecomunicaciones.
Este artículo determina sistemáticamente el índice cromático circular de grafos y multigrafos pequeños con grado máximo 4, 5 y 6, construye familias infinitas de tales grafos y refuta variantes de la "Conjetura del Hueco Superior" relacionadas con la conectividad de aristas.
Este artículo investiga el polinomio de dominación del grafo co-máximo del anillo de enteros módulo , derivando fórmulas explícitas para casos específicos que demuestran unimodalidad y log-concavidad, estableciendo expresiones estructurales para general y analizando las raíces de dominación mediante el teorema de Eneström-Kakeya.
Este artículo estudia una familia de instancias de Max-Cut ponderadas geométricamente, demostrando que existen umbrales críticos que determinan la optimalidad de cortes aislados específicos y proponiendo la conjetura de que estos cortes son globalmente óptimos para .
El artículo presenta el espectro de la matriz de adyacencia ponderada de grafos multipartitos completos, caracteriza sus familias con tres eigenvalores distintos, identifica matrices integrales, corrige resultados previos sobre la disminución de la energía y el radio espectral tras la eliminación de aristas, y resuelve problemas abiertos relacionados con la energía ISI y el espectro de grafos multipartitos coronados.
Este artículo identifica tres condiciones necesarias para la existencia de orientaciones acíclicas con paridad de grado entrante restringida, define y clasifica familias polinómicas de grafos donde dichas condiciones son suficientes, y proporciona algoritmos constructivos de tiempo polinomial para resolver el problema en dichas clases, incluyendo productos cartesianos de caminos y ciclos.
Este artículo demuestra que para hipergrafos definidos por subgrafos conexos y cruzamiento-libres de un grafo huésped de género acotado, existe un soporte (un grafo que conecta los vértices de cada hiperarista) que también posee género acotado, generalizando resultados previos sobre regiones no penetrantes y unificando el análisis de problemas de empaquetamiento y cobertura en superficies.
Este artículo estudia la densidad de aristas en dibujos de grafos que evitan un tipo específico de celda, estableciendo cotas superiores e inferiores para diversas combinaciones de estilos de dibujo y tipos de grafos, caracterizando completamente qué grafos simples admiten dibujos sin ciertas celdas y mejorando la cota inferior conocida para dibujos cuasiplanares no homotópicos.
Este artículo emplea el marco de localización para mejorar las cotas superiores existentes sobre el número de cliques en grafos con restricciones de grado máximo o longitud de camino, y proporciona caracterizaciones estructurales de los grafos extremos que alcanzan dichas cotas.
Este artículo demuestra que, para conjuntos de árboles filogenéticos con poca estructura común, el número de reticulaciones necesario para construir una red que los muestre todos es esencialmente la suma de las reticulaciones individuales, estableciendo límites inferiores que coinciden con las cotas superiores conocidas.
Este artículo construye autómatas para reconocer relaciones en secuencias -automáticas, establece una conexión entre la complejidad de subpalabras y la complejidad de estados de subsecuencias lineales, resuelve una pregunta reciente de Zantema y Bosma sobre el formato de dígitos más significativos primero, y analiza la complejidad computacional de dichas construcciones utilizando aritmética de Büchi.
Este artículo proporciona una demostración completa y válida de la cota superior para el número de doble dominación en grafos outerplanares maximales, corrigiendo una prueba previa incompleta presentada por Abd Aziz, Rad y Kamarulhaili.
Este artículo presenta fórmulas explícitas para los polinomios de posición general en grafos multipartitos completos, demuestra que estos polinomios son log-cóncavos y unimodales para partes de tamaño pero no para mayor, y prueba que la unimodalidad se conserva en coronas de ciertas clases de grafos.
El artículo demuestra que la brecha entre el tamaño mínimo de un circuito booleano y el de una fórmula en la base AIG es siempre 0 o 1, estableciendo que el uso compartido de puertas solo es necesario cuando hay al menos variables esenciales y que, cuando la brecha es 1, surge exclusivamente de un único nodo con fan-out 2.