Аноним

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

Материал из WEGA

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

Версия от 23:35, 15 сентября 2016

1443 байта добавлено ,  15 сентября 2016
→‎Применение
Строка 116: Строка 116:


== Применение ==
== Применение ==
Multi-connectivity problems are central in algorithmic graph theory and have numerous applications in computer science and operation research, see, e.g., [1,13, 11,18]. They also play very important role in the design of networks that arise in practical situations, see, e.g., [1,13]. Typical application areas include telecommunication, computer and road networks. Low degree connectivity problems for geometrical networks in the plane can often closely approximate such practical connectivity problems (see, e.g., the discussion in [13,17,18]). The survivable network design problem in geometric networks also arises in many applications, e. g., in telecommunication, communication network design, VLSI design, etc. [12,13,17,18].
Задачи о многосвязности занимают центральное место в алгоритмической теории графов и широко применяются в сферах вычислительных наук и исследования операций – см., например, [1, 13, 11, 18]. Они также играют исключительно важную роль в решении задач о построении сетей, возникающих во многих практических ситуациях [1, 13]. Среди типичных областей применения можно упомянуть телекоммуникации, компьютерные и улично-дорожные сети. Задачи о связности низкого уровня для геометрических сетей на плоскости нередко могут достаточно точно аппроксимировать подобные практические задачи (см., например, обсуждение в [13, 17, 18]). Задача построения сети с повышенной живучестью в геометрических сетях также возникает во множестве практических ситуаций – в частности, в телекоммуникациях, при проектировании сетей телекоммуникаций, проектировании СБИС и т.п. [12, 13, 17, 18].


Open Problems
The results discussed above lead to efficient algorithms only for small connectivity requirements k; the running-time is polynomial only for the value of k up to (log log n) for certain positive constant c < 1. It is an interesting open problem if one can obtain polynomial-time approximation schemes algorithms also for large values of k.


It is also an interesting open problem if the multi-connectivity problems in geometric networks can have practically fast approximation schemes.
== Открытые вопросы ==
Вышеприведенные результаты позволяют создавать эффективные алгоритмы только для малых значений требования связности k; время выполнения является полиномиальным только для значения k, не превышающего (log log n) для определенной положительной константы c < 1. Любопытно было бы узнать, можно ли получить алгоритм схемы аппроксимации с полиномиальным временем выполнения для больших значений k.
 
 
Еще один интересный открытый вопрос заключается в том, можно ли разработать достаточно быструю для практического применения схему аппроксимации задачи о многосвязности в геометрических сетях.


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

правка

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