Algoritmo óptimo para encontrar la circunferencia de un gráfico disperso?

Me pregunto cómo encontrar la circunferencia de un gráfico escaso no dirigido. Por disperso quiero decir . Por óptimo me refiero a la menor complejidad de tiempo. $|E|=O(|V|)$

Pensé en alguna modificación en el algoritmo de Tarjan para gráficos no dirigidos, pero no encontré buenos resultados. En realidad, pensé que si podía encontrar componentes conectados a 2 en , entonces podría encontrar la circunferencia, mediante algún tipo de inducción que se puede lograr desde la primera parte. Sin embargo, puedo estar en el camino equivocado. Cualquier algoritmo asintóticamente mejor que (es decir, ) es bienvenido. $O(|V|)$ $\Theta(|V|^2)$ $o(|V|^2)$

Probablemente este sea un problema abierto y quizás sea más adecuado para la teoría.

Aryabhata

Pero sería apropiado preguntar en teoría si este es un problema abierto.

JeffE

@Suresh, no puedo pensar mejor que para BFS. Además, si esto es adecuado para CStheory, lo preguntaré allí mañana.

Ω (n^{2})

$\Omega(n^2)$

Nota: esta pregunta ha sido transferida a cstheory. Votación para cerrar.

Suresh

@Suresh: En lugar de cerrar, deberíamos agregar una respuesta aquí con un enlace a la respuesta allí, diciendo que fue respondida en teoría. Además, ¿cómo lo cerraríamos? ¿Sin relación? (He agregado una respuesta CW).

Aryabhata

Respuestas:

Consulte Algoritmo óptimo para encontrar la circunferencia de un gráfico disperso de cstheory.SE que tiene una respuesta aceptada.

Aryabhata
fuente

Creo que la respuesta en CSTheory no está completa, estoy esperando más referencias, así que aún no la marqué como respuesta. Pero aquí puede decidir cerrar esto, pero no voy a eliminarlo porque creo que es bueno tener un historial de este problema en CS. PD: Sé que Shiva es excelente en campos relacionados, pero aun así creo que es mejor dejarlo abierto, puede que alguien más tenga mejores referencias.

@SaeedAmiri: Es posible que no siempre encuentres una referencia. Es posible que nadie haya considerado este problema antes o haya hecho una nota explícita en alguna lista de problemas abierta. Sin embargo, siempre puedes dejar tu pregunta sin marcar. por cierto, estoy en contra de cerrarlo aquí. Esta es una pregunta perfectamente válida para este sitio, y cerrarla podría dar una impresión equivocada a futuros interrogadores.

Aryabhata

Eche un vistazo a la pregunta de teoría ahora.

Suresh

Ver también Lecture on a Cycle in a Graph .

Pål GD