Encuentra ciclo negativo con restricciones de vértice

11

Dado un gráfico con aristas ponderadas, ¿cómo podemos encontrar un ciclo negativo que contenga al menos un vértice en un conjunto de vértices dado ? Gracias. $\{V_1, V_2, \ldots, V_k\}$

ds.algorithms graph-theory Tianyi Cui
fuente

Esta pregunta no está clara. ¿Pesos sobre qué, aristas o vértices? ¿Qué es

, es

un vértice o un conjunto de vértices?

{V_{1}, V_{2}, \dots, V_{k}}

$\{V_1, V_2, \dots, V_k\}$

V_{1}

$V_1$

Yixin Cao

@YixinCao Gracias por señalar, editado: peso en los bordes,

es un vértice.

V_{1}

$V_1$

Tianyi Cui

8

$V_i$ $V_i$ $V_i$ $V_i$ $O(nm)$

$V_1$ $S$ $T$ $G$ $V_1$ $N/2-0.01$ $V_1$ $S$ $T$ $V_1$

$v$ $(v,v')$

Neal Young
fuente

2

Me gusta esta respuesta mucho mejor que la mía.

David Eppstein

6

Voy a suponer que su entrada es un gráfico dirigido; No sé cómo hacer esto para el caso no dirigido.

$n$ $n$ $u$ $v$ $i$ $u$ $i+1$ $v$ $i$ $u$ $i$ $u$ $0$ $v$

Los ciclos en el gráfico expandido se proyectan nuevamente a ciclos en el gráfico original, pero cada ciclo en el gráfico expandido contiene uno de los vértices especificados (de lo contrario, no puede retroceder a través de las capas de expansión), por lo que el gráfico original contiene un ciclo negativo que contiene un vértice especificado si el gráfico expandido contiene algún ciclo negativo.

David Eppstein
fuente

n

$n$

m

$m$

n^{2}

$n^2$

n m

$nm$

O (n^{3} m)

$O(n^3m)$

2

Posiblemente más problemático, los ciclos que encuentra no necesariamente serán simples. ¿Requiere simples ciclos negativos?

David Eppstein

Encuentra ciclo negativo con restricciones de vértice

Respuestas: