Подсчет треугольников в неориентированном графике
Меня спросили об этом в интервью, и мне сказали, что O(n^2) возможно. У кого-нибудь есть простой подход к этому?
Нашел здесь статью, в которой говорится, что это так же сложно, как умножение матриц: http://kam.mff.cuni.cz/~matousek/cla/tria-mmult.pdf
2 ответа
Доказанная нижняя граница для алгоритма составления списка треугольников O(n^3) или O(m^1,5), здесь n - количество вершин, а m - количество ребер. Если вы хотите решить подсчет треугольников с помощью метода умножения матриц, сложность времени такая же, как и умножение матриц.
Вы должны перечислить более подробную информацию о вашем вопросе. Может быть, у графа есть какое-то особое свойство.
http://en.wikipedia.org/wiki/Triangle-free_graph
Проверка того, является ли граф свободным от треугольника, будет решена решением этой проблемы. O(n^2) должно было быть ошибкой со стороны интервьюеров.