52713

Автор(ов):

2

Параметры публикации
Тип публикации:
Статья в журнале/сборнике
Название:
Lower bound for the cost of connecting tree with given vertex degree sequence
Электронная публикация:
Да
ISBN/ISSN:
2051-1329
DOI:
10.1093/comnet/cnz031
Наименование источника:
Journal of Complex Networks
Город:
Oxford
Издательство:
Oxford University Press
Год издания:
2019
Страницы:
https://academic.oup.com/comnet/advance-article-abstract/doi/10.1093/comnet/cnz031/5550954
Аннотация
The optimal connecting network problem generalizes many models of structure optimization known from the literature, including communication and transport network topology design, graph cut and graph clustering, etc. For the case of connecting trees with the given sequence of vertex degrees the cost of the optimal tree is shown to be bounded from below by the solution of a semidefinite optimization program with bilinear matrix inequality constraints, which is reduced to the solution of a series of convex programs with linear matrix inequality constraints. The proposed lower-bound estimate is used to construct several heuristic algorithms and to evaluate their quality on a variety of generated and real-life datasets.
Библиографическая ссылка:
Губко М.В., Кузнецов А.В. Lower bound for the cost of connecting tree with given vertex degree sequence // Journal of Complex Networks. 2019. С. https://academic.oup.com/comnet/advance-article-abstract/doi/10.1093/comnet/cnz031/5550954.