Аноним

Минимальные k-связные геометрические сети: различия между версиями

Материал из WEGA

Минимальные k-связные геометрические сети (посмотреть исходный код)

Версия от 15:00, 14 сентября 2016

35 байт убрано ,  14 сентября 2016
→‎Нотация
Нет описания правки
Строка 44: Строка 44:




Задача конструирования сети с повышенной живучестью
'''Задача конструирования сети с повышенной живучестью'''
For a given set S of points in R and a connectivity requirement function r:SxS^-N, find a minimum-cost geometric network spanning points in S such that for any pair of vertices p;q 2 S the sub-network has грл internally vertex-disjoint (or edge-disjoint, respectively) paths between p and q.
 
For a given set S of points in R and a connectivity requirement function r:SxS^-N, find a minimum-cost geometric network spanning points in S such that for any pair of vertices p;q 2 S the sub-network has грл internally vertex-disjoint (or edge-disjoint, respectively) paths between p and q.
Для заданного набора S точек в R и функции обеспечения связности r:SxS^-N найти геометрическую сеть минимальной стоимости, охватывающую точки из S, такую, что для любой пары вершин p, q 2 S подсеть имеет грл внутренних вершинно-непересекающихся (или реберно-непересекащихся, соответственно) путей между p и q.




Строка 107: Строка 107:


It is also an interesting open problem if the multi-connectivity problems in geometric networks can have practically fast approximation schemes.
It is also an interesting open problem if the multi-connectivity problems in geometric networks can have practically fast approximation schemes.


== См. также ==
== См. также ==
Irina
4551

правка

Источник — http://pco.iis.nsk.su/wega/index.php/Служебная:Сравнение_версий/11833