¿Cuál es el mejor resultado determinista para mantener el cierre transitivo dinámico en un gráfico dirigido con solo inserción de borde? Leí algunos documentos sobre el problema de cierre transitivo dinámico con inserción y eliminación de bordes. Sin embargo, ¿hay algún algoritmo mejor para eso...
Sean conjuntos que pueden tener elementos en común. Estoy buscando un conjunto X más pequeño tal que ∀ i ,S1, S2, ... , SnorteS1,S2,...,SnorteS_1,S_2,\ldots,S_nXXX .∀ i ,X∩ Syo≠ ∅∀yo,X∩Syo≠∅\forall i,\,X\cap S_i \ne \emptyset ¿Este problema tiene un nombre? ¿O se reduce a algún problema...
Tome un gráfico dirigido donde los bordes estén decorados con un número natural. Queremos el conjunto de todas las rutas entre dos vértices y modo que cada borde sucesivo en la ruta esté decorado con un número natural que sea mayor que el número natural que decora el borde
Una cubierta de borde es un subconjunto de bordes de un gráfico de tal manera que cada vértice del gráfico es adyacente al menos a un borde de la cubierta. Los siguientes dos artículos dicen que las cubiertas de borde de conteo, se #P -Complete: A FPTAS simples para el recuento de cubiertas de...
En forma simple: ¿Puede un autómata finito bidireccional reconocer gráficos vértice que contienen un triángulo con estados ?vvvo(v3)o(v3)o(v^3) Detalles Aquí son de interés los gráficos vértice codificados usando una secuencia de aristas, cada arista es un par de vértices distintos de...
Supongamos que queremos encontrar o max x ∏ i j ∈ E f(xi,xj)∑x∏ij∈Ef(xi,xj)∑x∏ij∈Ef(xi,xj)\sum_x \prod_{ij \in E} f(x_i,x_j)maxx∏ij∈Ef(xi,xj)maxx∏ij∈Ef(xi,xj)\max_x \prod_{ij \in E} f(x_i,x_j) Donde Max o la suma se toma sobre todos los marcajes de VVV , el producto se toma sobre todos los...
Una extensión clásica del problema del flujo máximo es el problema del "flujo máximo en el tiempo": se le da un dígrafo, dos de los cuales se distinguen como la fuente y el sumidero, donde cada arco tiene dos parámetros, una capacidad por -unidad-tiempo y un retraso. También se le dará un horizonte...
¿Cuáles son buenos documentos / libros para comprender mejor el poder de la descomposición modular y sus propiedades? Estoy particularmente interesado en los aspectos algorítmicos de la descomposición modular. He oído que es posible encontrar una descomposición modular de un gráfico en tiempo...
El problema kkk -cycle es el siguiente: Instancia: un gráfico no dirigido solsolGcon nnn vértices y hasta aristas.(n2)(n2)n \choose 2 Pregunta: ¿Existe un ciclo (adecuado) en ?GkkkGGG Antecedentes: para cualquier fija , podemos resolver el ciclo en el tiempo .2 k O ( n 2
Estoy tratando de entender algunos conceptos sobre la descomposición modular y los gráficos de ancho de camarilla. En este documento ("En gráficos P4-tidy"), hay una prueba de cómo resolver problemas de optimización como el número de camarilla o el número cromático usando la descomposición...
Hace aproximadamente un año, un amigo y yo pensamos en una forma de implementar el algoritmo de Kruskal para gráficos densos en un límite mejor que el habitual (sin suponer aristas previamente ordenadas). Específicamente, logramos en todos los casos, similar a Prim cuando se implementa usando...
¿Cuál es la complejidad del siguiente problema? Entrada : HHH un camino hamiltoniano en KnKnK_n R⊆[n]2R⊆[n]2R \subseteq [n]^2 un subconjunto de pares de vértices un entero positivo kkk Consulta : ¿hay una M coincidente tal que para cada ( v , u ) ∈ R , d G ( v , u ) ≤ k ? (donde G = ( [ n ] ,...
Sea G un gráfico no dirigido de n-nodos, y sea T un subconjunto de nodos de V (G) llamados terminales . Un preservador de distancia de (G, T) es un gráfico H que satisface la propiedad reH( u , v ) = dsol( u , v )reH(tu,v)=resol(tu,v)d_H(u,v) = d_G(u,v) para todos los nodos u, v en T. (Tenga en...
El algoritmo húngaro es un algoritmo de optimización combinatoria que resuelve el problema de coincidencia bipartita de peso máximo en tiempo polinómico y anticipa el desarrollo posterior del importante método primal-dual . El algoritmo fue desarrollado y publicado por Harold Kuhn en 1955, quien...
Sabemos que el algoritmo de mincut de Karger se puede usar para demostrar (de manera no constructiva) que el número máximo de mincuts posibles que puede tener un gráfico es .(n2)(n2)n \choose 2 Me preguntaba si podríamos de alguna manera probar esta identidad al dar una prueba biyectiva (más bien...
Se ha demostrado que la propagación de creencias es un método muy poderoso a través de la investigación en modelos gráficos probabilísticos. Sin embargo, no sé nada sobre BP que sea comparable a los métodos MCMC donde podemos tener esquemas de aproximación aleatoria totalmente polinomiales (FPRAS)...
El problema del camino más largo es NP-hard. La prueba (¿típica?) Se basa en una reducción del problema del camino hamiltoniano (que es NP completo). Tenga en cuenta que aquí la ruta se considera simple (nodo). Es decir, ningún vértice puede ocurrir más de una vez en el camino. Obviamente, también...
Dado un grafo, G=(V,E)G=(V,E)G = (V, E) , quiero encontrar un óptimo -domination para . Es decir, quiero un subconjunto de tal que todos los vértices enrrrGGGSSSVVVGGG están a una distancia de como máximo rrr de algún vértice en SSS , mientras se minimiza el tamaño de SSS . De lo que he verificado...
Estoy implementando alguna parte del sistema que requiere ayuda. Por lo tanto, lo estoy enmarcando como un problema gráfico para que sea independiente del dominio. Problema: se nos da un gráfico acíclico dirigido . Sin pérdida de generalidad, suponga que G tiene exactamente un vértice fuente s y...
Dado un gráfico cíclico dirigido donde el peso de cada borde puede ser negativo, el concepto de "camino más corto" solo tiene sentido si no hay ciclos negativos, y en ese caso puede aplicar el algoritmo Bellman-Ford. Sin embargo, estoy interesado en encontrar el camino más corto entre dos vértices...