Dado un lenguaje regular (NFA, DFA, gramática o expresión regular), ¿cómo se puede contar el número de palabras aceptadas en un idioma determinado? Tanto "con exactamente n letras" como "con como máximo n letras" son de interés. Margareta Ackerman tiene dos documentos sobre el tema relacionado de...
Definimos un lenguaje de árbol regular como en el libro TATA : es el conjunto de árboles aceptado por un autómata de árbol finito no determinista (Capítulo 1) o, de manera equivalente, el conjunto de árboles generado por una gramática de árbol regular (Capítulo 2). Ambos formalismos se parecen...
El lema de regularidad de Szemeredi dice que cada gráfico denso puede aproximarse como una unión de O(1)O(1)O(1) muchos gráficos expansores bipartitos. Más exactamente, hay una partición de la mayoría de los vértices en conjuntos O(1)O(1)O(1) tal manera que la mayoría de los pares de conjuntos...
Para cualquier , digo que una secuencia s de enteros en { 1 , ... , n } es n -completa si, para cada permutación p de { 1 , ... , n } , se escribe como una secuencia de enteros distintos por pares p 1 , ... , p n , la secuencia p es una subsecuencia de s , es decir, existe 1 ≤ i 1 < i 2n >...
El resultado por Robertson y Seymour demuestra un algoritmo para comprobar que es un gráfico fijo G es un menor de H . Tengo dos preguntas y media sobre este tema:O ( n3)O(norte3)O(n^3)solsolGHHH 1) Parece que ha habido mejoras en este algoritmo desde entonces. ¿Cuál es el algoritmo más conocido...
Volumen III de Knuth de The Art of Computer Programming (capítulo 5, verso 3.2) incluye la siguiente tabla que enumera el exacto número mínimo de comparaciones requeridas para seleccionar el -ésimo elemento más pequeño de un conjunto sin ordenar de tamaño , para todos . Esta tabla, junto con las...
¿Se ha estudiado la complejidad del siguiente problema? Entrada : un gráfico cúbico (o regular) , un límite superior naturalG = ( V , E ) t333G = ( V, E)G=(V,E)G=(V,E)ttt Pregunta : ¿hay una partición de en partes de tamaño modo que la suma de los órdenes de los subgrafos correspondientes (no...
Dado un gráfico no dirigido y no ponderado y un entero par , ¿cuál es la complejidad computacional de contar conjuntos de vértices tal que y el subgrafo de restringido al conjunto de vértices admite una combinación perfecta? ¿La complejidad # P-completa? ¿Hay alguna referencia para este problema?k...
Problema de matrimonio estable: http://en.wikipedia.org/wiki/Stable_marriage_problem Soy consciente de que para una instancia de un SMP, son posibles muchos otros matrimonios estables, aparte del que devuelve el algoritmo Gale-Shapley. Sin embargo, si solo se nos da , el número de hombres /...
La conjetura de reconstrucción dice que los gráficos (con al menos tres vértices) están determinados únicamente por sus subgrafos eliminados de vértices. Esta conjetura tiene cinco décadas. Al buscar literatura relevante, descubrí que se sabe que las siguientes clases de gráficos son...
Sé que es indecidible determinar si un conjunto de fichas puede enlosar el plano, como resultado de que Berger usa fichas de Wang . Mi pregunta es si también se sabe que es indecidible determinar si un solo mosaico dado puede enlosar el plano, un mosaico monoédrico . Si esto sigue sin resolverse,...
Estoy tratando de encontrar qué tan cerca están realmente y E [ t w ( G ) ] , cuando G ∈ G ( n , p = c / n ) y c > 1 es una constante que no depende de n (entonces E [ t w ( G ) ] = Θ ( n ) ). Mi estimación es que t w ( G ) ≤t w ( G )tw(sol)tw(G)mi[ t w ( G ) ]mi[tw(sol)]E[tw(G)]G ∈ G ( n , p =...
Para A⊂[n]UNA⊂[norte]A\subset [n] denotan por aiunayoa_i el ithyothi^{th} elemento más pequeño de AUNAA . Para dos conjuntos de elementos kkk , A,B⊂[n]A,B⊂[n]A,B\subset [n] , decimos que A≤BA≤BA\le B si ai≤biai≤bia_i\le b_i para cada iii . A kkk hypergraph Uniform que se llama una cadena cambio...
( Publiqué esta pregunta en MathOverflow hace dos semanas, pero hasta ahora sin una respuesta rigurosa) Tengo una pregunta sobre las medidas de ancho de gráficos de gráficos simples no dirigidos. Es bien sabido que los cográficos (gráficos que pueden construirse mediante las operaciones de unión y...
Dado un conjunto de personas, me gustaría sentarlas para una secuencia de comidas en mesas de tamaño k . (Por supuesto, hay suficientes mesas para sentarse todas | S | para cada comida.) Me gustaría organizar esto de tal manera que nadie comparta una mesa con la misma persona dos veces. Los valores...
¿Dónde puedo encontrar gráficos relevantes para problemas de la vida real? Dos repositorios que conozco son: Colección de matriz dispersa de la Universidad de Florida TreewidthLib de
Publicación actualizada el 31 de agosto : agregué un resumen de las respuestas actuales debajo de la pregunta original. Gracias por todas las respuestas interesantes! Por supuesto, todos pueden seguir publicando cualquier hallazgo nuevo. ¿Para qué familias de gráficos existe un algoritmo de...
Si tengo un conjunto de restricciones lineales en las que cada restricción tiene como máximo (por ejemplo) 4 variables (todas no negativas y con coeficientes {0,1} excepto una variable que puede tener un coeficiente -1), qué se sabe sobre la solución ¿espacio? Me preocupa menos una solución...
Sé que trivialmente la función OR en nortenn variables X1, ... , xnortex1,…,xnx_1,\ldots, x_n puede representarse exactamente por el polinomio p ( x1, ... , xnorte)p(x1,…,xn)p(x_1,\ldots,x_n) como tal: p ( x1, ... , xnorte) = 1 - ∏nortei = 1( 1 - xyo)p(x1,…,xn)=1−∏i=1n(1−xi)p(x_1,\ldots,x_n) =...
El tiempo de conmutación en un gráfico conectado se define como el número esperado de pasos en una caminata aleatoria que comienza en , antes de que se visite el nodo y luego se vuelva a alcanzar el nodo . Básicamente es la suma de los dos tiempos de golpeo y .i j i H ( i , j ) H ( j , i )G = ( V,...