2017/05/11 by Mikhail Goubko, Goubko, Mikhail
Computer Science · Mathematics · #Combinatorics (math.CO) #Computational Drug Discovery Methods #FOS: Mathematics #Graph Labeling and Dimension Problems #Graph Theory and Algorithms #Graph theory and applications #Interconnection Networks and Systems
paper · pdf · doi:10.48550/arxiv.1705.04291
openalex publication_date 2017/05/11 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
The Wiener index is maximized over the set of trees with the given vertex\nweight and degree sequences. This model covers the traditional "unweighed"\nWiener index, the terminal Wiener index, and the vertex distance index. It is\nshown that there exists an optimal caterpillar. If weights of internal vertices\nincrease in their degrees, then an optimal caterpillar exists with weights of\ninternal vertices on its backbone monotonously increasing from some central\npoint to the ends of the backbone, and the same is true for pendent vertices. A\ntight upper bound of the Wiener index value is proposed and an efficient greedy\nheuristics is developed that approximates well the optimal index value.\nFinally, a branch and bound algorithm is built and tested for the exact\nsolution of this NP-complete problem.\n