4551
правка
Минимальные k-связные геометрические сети: различия между версиями
Перейти к навигации
Перейти к поиску
Минимальные k-связные геометрические сети (посмотреть исходный код)
Версия от 15:31, 14 сентября 2016
, 14 сентября 2016→Нотация
Irina (обсуждение | вклад) м (→Нотация) |
Irina (обсуждение | вклад) |
||
| Строка 49: | Строка 49: | ||
Во многих приложениях этой задачи, нередко считающихся наиболее интересными [9, 13], функция требования связности определяется при помощи функции от одного аргумента, присваивающей каждой вершине p ее тип связности rv 2 N. Тогда для любой пары вершин p, q 2 S требование связности Грл задается просто в виде minfrp; rqg [12, 13, 17, 18]. Этот список включает задачу о вычислении дерева Штейнера, (см., например, [ ]), в которой rp 2 f0; 1g для любой вершины p2S. | |||
Схема аппроксимации с полиномиальным временем исполнения (PTAS) представляет собой семейство алгоритмов fA" g, такое, что для каждого фиксированного " > 0 алгоритм A" исполняется за время, полиномиальное относительно размера входного графа, и дает (1 + ")-аппроксимацию. | |||
== Родственные работы == | |||
For a very extensive presentation of results concerning problems of finding minimum-cost k-vertex- and k-edge-connected spanning subgraphs, non-uniform connectivity, connectivity augmentation problems, and geometric problems, see [1,3,11,15]. | For a very extensive presentation of results concerning problems of finding minimum-cost k-vertex- and k-edge-connected spanning subgraphs, non-uniform connectivity, connectivity augmentation problems, and geometric problems, see [1,3,11,15]. | ||