Prueba / identificación de una clasificación topológica

Que le den un conjunto de Dirigido acíclicos gráficos sobre el mismo conjunto de vértices . También se le da una permutación del conjunto de vértices . ¿Cuál es el mejor algoritmo que podría identificar los gráficos entre que tienen como un tipo topológico? ¿Podría alguien probar si es una especie topológica de un DAG sobre en tiempo sub-lineal? $n$ $G_1, G_2, ..., G_n$ $m$ $V$ $(v_1,v_2,...,v_m)$ $G_1, G_2, ..., G_n$ $(v_1,v_2,...,v_m)$ $(v_1,v_2,...,v_m)$ $G$ $V$

ds.algorithms graph-algorithms directed-acyclic-graph Hsien-Chih Chang 張顯之
fuente

¿Puede construir una estructura de datos basada en el conjunto de gráficos antes de que se le presente el orden de los vértices? Debe observar todos los gráficos

y todos los bordes

en el orden, por lo que, a menos que se le permita preprocesar los gráficos de alguna manera, no parece que pueda vencer el tiempo lineal.

n

$n$

m - 1

$m-1$

mjqxxxx

Hsien-Chih Chang, ¿cuál sería una buena técnica de preprocesamiento que pueda permitir una mejor solución? ¿Algún tipo de hashing? Supongo que puedes vencer el tiempo lineal si puedes aproximar la solución (algoritmo probabilístico).

user2471

@ user2471: Como dije en tu respuesta anterior, esta publicación fue escrita por @Steve, no yo;)

Hsien-Chih Chang 張顯之

Lo siento Hsien-Chih Chang, mi pregunta fue para todos :)

user2471

@ user2471, ¡no es necesario disculparse! Espero que alguien que esté familiarizado con esta pregunta publique una buena respuesta: D

Hsien-Chih Chang 張顯之

Respuestas:

Esto se puede hacer en un tiempo casi lineal.

Deje que la permutación sea , y deje que sea el número de pasos necesarios para verificar una sola arista contra . Entonces es suficiente verificar que cada uno de los bordes de sea compatible con , lo que se puede hacer en el tiempo u $\pi = (v_1,\dots,v_m)$ $k = k(\pi)$ $(u,v)$ $\pi$ $M_i$ $G_i$ $\pi$ $O(kM_i)$ general. $O(k\sum M_i)$

Al preprocesar se puede reducir a dos búsquedas en una matriz que contiene entradas cada una de $\pi$ $k$ $m$ tamaño , y una comparación entre dosentradas -bit en la matriz; el elemento de matriz contiene el índice de en considerado como una lista ordenada. Esto significa que $\log\, m$ $(\log\ m)$ $a[w]$ $w$ $\pi$ produciendo $k = O(\log\, m)$ tiempo total para el límite superior. $O((\log\, m)\sum M_i)$

Como @mjqxxxx señala, cada borde de cada gráfico puede ser relevante. Esto crea un límite inferior de pasos de , donde $\Omega(K\sum M_i)$ $K$ es la menor cantidad de trabajo que debe hacerse para cada borde del gráfico; es posible que algunos enfoques puedan amortizar el costo para que . Esto todavía va a ser $K = o(\log\, m)$ $\Omega(\sum M_i)$ en el mejor de los casos, por lo que no queda mucho espacio.

András Salamon
fuente

Qué algoritmo se puede usar para hacer k = log m. ¿Es sufijo de árboles?

vincent mathew

Método trivial

GS = {G1,G2...G3}
for v in (v1,v2,...vm)
      remove all graphs from GS where indegree(v) != 0
      remove v and attached edges from remaining GS

No es tan rápido como quieras. Pero resuelve un problema de que "puede haber múltiples ordenamientos topológicos válidos de DAG". Y encontrarlos a todos no es una buena idea.

Pratik Deoghare
fuente