Algorithme optimal pour trouver la circonférence d'un graphique clairsemé?

Je me demande comment trouver la circonférence d'un graphe non orienté clairsemé. Par clairsemés, je veux dire . Par optimal, j'entends la complexité temporelle la plus faible. $|E|=O(|V|)$

J'ai pensé à une modification de l'algorithme de Tarjan pour les graphiques non orientés, mais je n'ai pas trouvé de bons résultats. En fait, je pensais que si je pouvais trouver un 2 composants connectés dans , alors je peux trouver la circonférence, par une sorte d'induction qui peut être obtenue à partir de la première partie. Je suis peut-être sur la mauvaise voie, cependant. Tout algorithme asymptotiquement meilleur que (ie ) est le bienvenu. $O(|V|)$ $\Theta(|V|^2)$ $o(|V|^2)$

C'est probablement encore un problème ouvert et peut-être mieux adapté à la théorie.

Aryabhata

Mais il conviendrait de demander sur la théorie s'il s'agit d'un problème ouvert.

JeffE

@Suresh, je ne peux pas penser mieux que

pour BFS. De plus, si cela convient à CStheory, je le demanderai demain.

Ω (n^{2})

$\Omega(n^2)$

Remarque: cette question a été transférée dans cstheory. Voter pour clore.

Suresh

@Suresh: Plutôt que de clôturer, nous devrions simplement ajouter une réponse ici avec un lien vers la réponse là-bas, en disant qu'elle a été répondue dans cstheory. D'ailleurs, comment le fermerions-nous? Hors sujet? (J'ai ajouté une réponse CW).

Aryabhata

Réponses:

Voir Algorithme optimal pour trouver la circonférence d'un graphe clairsemé de cstheory.SE qui a une réponse acceptée.

Aryabhata
la source

Je pense que la réponse dans CSTheory n'est pas complète, j'attends plus de références donc je ne l'ai pas encore marqué comme réponse. Mais ici, vous pouvez décider de fermer cela, mais je ne vais pas le supprimer car je pense que c'est bien d'avoir l'historique de ce problème dans CS. PS: Je sais que Shiva est excellent dans des domaines connexes, mais je pense quand même qu'il vaut mieux le laisser ouvert, peut-être que quelqu'un d'autre a de meilleures références.

@SaeedAmiri: Vous ne trouverez peut-être pas toujours une référence. Il est possible que personne n'ait considéré ce problème auparavant ou n'en ait fait une note explicite dans une liste de problèmes ouverts. Vous pouvez toujours laisser votre question sans marque. btw, je suis contre la fermeture ici. C'est une question parfaitement valable pour ce site, et la fermer pourrait donner une mauvaise impression aux futurs intervenants.

Aryabhata

jetez un oeil à la question de la théorie maintenant.

Suresh

Voir aussi Conférence sur un cycle dans un graphique .

Pål GD