Algoritmo ideal para encontrar a circunferência de um gráfico esparso?

Gostaria de saber como encontrar a circunferência de um gráfico esparso e não direcionado. Por esparso, quero dizer . Por ótimo, quero dizer a menor complexidade de tempo. $|E|=O(|V|)$

Pensei em alguma modificação no algoritmo de Tarjan para gráficos não direcionados, mas não encontrei bons resultados. Na verdade, eu pensei que, se eu pudesse encontrar componentes com 2 conexões em , então eu poderia encontrar a circunferência, por algum tipo de indução que pode ser alcançada desde a primeira parte. Eu posso estar no caminho errado, no entanto. Qualquer algoritmo assintoticamente melhor que (ou seja, ) é bem-vindo. $O(|V|)$ $\Theta(|V|^2)$ $o(|V|^2)$

Provavelmente esse ainda é um problema em aberto e talvez mais adequado para a história.

Aryabhata

Mas seria apropriado perguntar sobre a história se esse é um problema em aberto.

jeffe

@ Suresh, não consigo pensar melhor que para BFS. Além disso, se isso for adequado para o CStheory, solicitarei amanhã.

Ω (n^{2})

$\Omega(n^2)$

Nota: esta questão foi transferida para cstheory. Votação para fechar.

Suresh

@Suresh: Em vez de fechar, devemos adicionar uma resposta aqui com um link para a resposta, dizendo que ela foi respondida na história. Além disso, como o fecharíamos? Fora do assunto? (Eu adicionei uma resposta CW).

Aryabhata

Respostas:

Consulte o algoritmo ideal para encontrar a circunferência de um gráfico esparso do cstheory.SE, que possui uma resposta aceita.

Aryabhata
fonte

Eu acho que a resposta no CSTheory não está completa, estou esperando por mais referências, então ainda não a marquei como resposta. Mas aqui você pode decidir encerrar isso, mas não vou excluí-lo porque acho bom ter um histórico desse problema no CS. PS: Eu sei que Shiva é excelente em áreas afins, mas ainda acho que é melhor deixar em aberto, pode ser que alguém tenha melhores referências.

@SaeedAmiri: Nem sempre você encontra uma referência. É possível que ninguém tenha considerado esse problema antes ou feito uma anotação explícita em alguma lista de problemas aberta. Você sempre pode deixar sua pergunta sem marcação. Aliás, sou contra fechá-lo aqui. Essa é uma pergunta perfeitamente válida para este site, e fechar isso pode causar uma impressão errada aos futuros questionadores.

Aryabhata

dê uma olhada na questão da história agora.

Suresh

Veja também Palestra sobre um ciclo em um gráfico .

Pål GD