Weighted girth problem: различия между версиями

Материал из WEGA
Перейти к навигации Перейти к поиску
(Новая страница: «'''Weighted girth problem''' --- задача о взвешенном обхвате. Given a weighted undirected graph <math>G</math>, the '''weighted girth probl…»)
 
(нет различий)

Текущая версия от 14:54, 30 августа 2011

Weighted girth problem --- задача о взвешенном обхвате.

Given a weighted undirected graph [math]\displaystyle{ G }[/math], the weighted girth problem (WGP) is to find a cycle having minimal weight. This problem is in general NP-hard but it can be solved in polynomial time, when [math]\displaystyle{ G }[/math] does not contain any cycle of a negative weight.

If we force the length of the cycle in the WGP to be less than some value [math]\displaystyle{ k }[/math], we obtain the cardinality constrained circuit problem (CCCP). If the cycle in WGP is forced to go through all vertices of [math]\displaystyle{ V(G) }[/math], we obtain the well-known traveling salesman problem.