¿Cómo puedo determinar la cantidad de rutas simples únicas dentro de un gráfico no dirigido? Ya sea para una determinada longitud o para un rango de longitudes aceptables.
Recuerde que una ruta simple es una ruta sin ciclos, así que estoy hablando de contar el número de rutas sin ciclo.
Respuestas:
Hay varios algoritmos que cuentan las rutas simples de longitud en el tiempo f ( k ) n k / 2 + O ( 1 ) , que es mucho mejor que la fuerza bruta (tiempo O ( n k ) ). Ver, por ejemplo, Vassilevska y Williams, 2009 .k f(k)nk/2+O(1) O(nk)
fuente
Es # P-completo (Valiant, 1979), por lo que es poco probable que lo haga mucho mejor que la fuerza bruta, si desea la respuesta exacta. Las aproximaciones son discutidas por Roberts y Kroese (2007).
B. Roberts y DP Kroese, " Estimación del número de rutas - t en un gráficos t ". Journal of Graph Algorithms and Applications , 11 (1): 195-214, 2007.
LG Valiant, " La complejidad de los problemas de enumeración y confiabilidad ". SIAM Journal on Computing 8 (3): 410-421, 1979.
fuente
Me gustaría agregar otro algoritmo de aproximación, uno parametrizado: para un fijo > 0 (o más precisamente, δ = Ω ( 1δ>0 ), puede calcularunaaproximación(1+δ)del número de rutas simples, en un gráfico dirigido o no dirigido, de longitudken el tiempoO∗(2O(k)).δ=Ω(1poly(k)) (1+δ) k O∗(2O(k))
fuente