Вычисление таких известных характеристик связности, как вероятность связности выделенного подмножества вершин, математическое ожидание числа несвязных пар вершин, средняя длина кратчайшего пути и многие другие, в общем случае представляет из себя NP-трудную задачу. Однако содержательный смысл показателей зачастую позволяет находить решение за полинамиальное время для некоторых классов графов в одних случаях, и существенно снижать объём вычислений в других. Наиболее подробно рассматривается задача вычисления коэффициентов полинома связности для случайных графов с ненадёжными рёбрами.
Примечание. Тезисы докладов публикуются в авторской редакции
Ваши комментарии Обратная связь |
[Головная страница] [Конференции] |
© 2007, Институт Вычислительной Математики и Математической Геофизики СО РАН, Новосибирск
© 2007, Сибирское отделение Российской академии наук, Новосибирск
Дата последней модификации: 06-Jul-2012 (11:52:51)