2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




 
 NP-трудна ли задача вычисления надежности решетки?
Сообщение19.10.2008, 16:22 
Дана решетка. Выделены два терминала: в нижнем левом углу и верхнем правом углу. Каждому ребру сопоставлена его надежность (вероятность связности) p\in(0,1).
Вот мне интересно, задача вычисления надежности решетки (вероятности связности терминалов) NP-трудная? То есть может кто видел ссылку на конкретную работу..Я не видела.
Мне кажется, что да. Во многих статьях, при анализе алгоритмов вычисления надежности графа, часто в качестве тестовых графов используют решетки, типа как нехорошие примеры.. Заранее большое спасибо за любую помощь :)

 
 
 [ 1 сообщение ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group