Lower bound for the cost of connecting tree with given vertex degree sequence

DOI10.1093/COMNET/CNZ031zbMATH Open1472.05137arXiv1808.06199OpenAlexW2968172275WikidataQ127439758 ScholiaQ127439758MaRDI QIDQ4958799FDOQ4958799

Authors:

Publication date: 15 September 2021

Published in: Journal of Complex Networks (Search for Journal in Brave)

Abstract: 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, structure identification from data, 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 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 data sets. Keywords: Optimal communication network, generalized Wiener index, origin-destination matrix, semidefinite programming, quadratic matrix inequality.

Full work available at URL: https://arxiv.org/abs/1808.06199

Recommendations

• Bounded-degree spanning tree problems: models and new algorithms
• scientific article; zbMATH DE number 3891405
• Near-optimal bounded-degree spanning trees
• Approximation algorithms for degree-constrained minimum-cost network-design problems
• Degree bounded network design with metric costs

zbMATH Keywords

semidefinite programmingbilinear matrix inequalitygeneralized Wiener indexorigin-destination matrixoptimal communication network

Mathematics Subject Classification ID

Semidefinite programming (90C22) Graphical indices (Wiener index, Zagreb index, Randi? index, etc.) (05C09) Small world graphs, complex networks (graph-theoretic aspects) (05C82) Vertex degrees (05C07)

Cited In (1)

• Bilinear matrix equation characterizes Laplacian and distance matrices of weighted trees

This page was built for publication: Lower bound for the cost of connecting tree with given vertex degree sequence

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4958799)