Оптимальный алгоритм нахождения обхвата разреженного графа?

Интересно, как найти обхват разреженного неориентированного графа. Под редким я подразумеваю . Под оптимальным я подразумеваю минимальную временную сложность. $|E|=O(|V|)$

Я думал о некоторой модификации алгоритма Тарьяна для неориентированных графов, но я не нашел хороших результатов. На самом деле я думал, что если бы я мог найти 2-связные компоненты в , то я мог бы найти обхват посредством некоторой индукции, которая может быть достигнута из первой части. Возможно, я не на том пути. Любой алгоритм, асимптотически лучше, чем (т. ), приветствуется. $O(|V|)$ $\Theta(|V|^2)$ $o(|V|^2)$

Вероятно, это все еще открытая проблема и, возможно, лучше подходит для теории.

Арьябхата

Но было бы уместно спросить о том, является ли это открытой проблемой.

Джефф

@ Суреш, я не могу думать лучше, чем для BFS. Также, если это подходит для CStheory, я спрошу это там завтра.

Ω (n^{2})

$\Omega(n^2)$

Примечание: этот вопрос был перенесен в историю. Голосование, чтобы закрыть.

Суреш

@Suresh: Вместо того, чтобы закрывать, мы должны просто добавить здесь ответ со ссылкой на него, сказав, что на него был дан ответ в cstheory. Кроме того, чем бы мы это закрыли? Не по теме? (Я добавил CW ответ).

Арьябхата

Ответы:

См. Оптимальный алгоритм для поиска обхвата разреженного графа в cstheory.SE, который имеет принятый ответ.

Aryabhata
источник

Я думаю, что ответ в CSTheory не завершен, я жду больше ссылок, поэтому я еще не пометил его как ответ. Но здесь вы можете решить закрыть это, но я не собираюсь удалять это, потому что я думаю, что хорошо иметь историю этой проблемы в CS. PS: я знаю, что Шива превосходен в смежных областях, но все же я думаю, что лучше оставить это открытым, может быть, у кого-то еще есть лучшие рекомендации.

@SaeedAmiri: Вы не всегда можете найти ссылку. Вполне возможно, что никто не рассматривал эту проблему раньше или не делал явных указаний на нее в каком-то открытом списке проблем. Вы всегда можете оставить свой вопрос без отметки, хотя. Кстати, я против закрытия здесь. Это совершенно правильный вопрос для этого сайта, и закрытие его может создать неправильное впечатление для будущих спрашивающих.

Арьябхата

взгляните на главный вопрос сейчас.

Суреш

Смотрите также Лекция о цикле на графике .

Пол Г.Д.