Optimizing Wiener and Randic Indices of Graphs

被引:1
作者
Mahasinghe, A. C. [1 ]
Erandi, K. K. W. H. [1 ]
Perera, S. S. N. [1 ]
机构
[1] Univ Colombo, Fac Sci, Res & Dev Ctr Math Modeling, Dept Math, Colombo 03, Sri Lanka
基金
美国国家科学基金会;
关键词
TOPOLOGICAL INDEXES; PRODUCT DESIGN; HARARY INDEX; OPTIMIZATION; NETWORKS; COMPUTE; BOUNDS;
D O I
10.1155/2020/3139867
中图分类号
C93 [管理学]; O22 [运筹学];
学科分类号
070105 ; 12 ; 1201 ; 1202 ; 120202 ;
摘要
Wiener and Randic indices have long been studied in chemical graph theory as connection strength measures of graphs. Later, these indices were used in different fields such as network analysis. We consider two optimization problems related to these indices, with potential applications to network theory, in particular to epidemiological networks. Given a connected graph and a fixed total edge weight, we investigate how individual weights must be assigned to edges, minimizing the connection strength of the graph. In order to measure the connection strength, we use the weighted Wiener index and a modified version of the ordinary Randic index. Wiener index optimization is linear, while Randic index optimization turns out to be both nonlinear and nonconvex. Hence, we adopt the technique of separable programming to generate solutions. We present our experimental results by applying relevant algorithms to several graphs.
引用
收藏
页数:10
相关论文
共 61 条
  • [1] Separable programming/duality approach to solving the multi-product Newsboy/Gardener Problem with linear constraints
    Abdel-Malek, Layek L.
    Otegbeye, Mojisola
    [J]. APPLIED MATHEMATICAL MODELLING, 2013, 37 (06) : 4497 - 4508
  • [2] On reliability indices of communication networks
    Alberto Rodriguez-Velazquez, Juan
    Kamisalic, Aida
    Domingo-Ferrer, Josep
    [J]. COMPUTERS & MATHEMATICS WITH APPLICATIONS, 2009, 58 (07) : 1433 - 1440
  • [3] Some bounds for the connectivity index of a chemical graph
    Araujo, O
    De la Pena, JA
    [J]. JOURNAL OF CHEMICAL INFORMATION AND COMPUTER SCIENCES, 1998, 38 (05): : 827 - 831
  • [4] A SEPARABLE PROGRAMMING APPROACH TO THE LINEAR COMPLEMENTARITY-PROBLEM
    BARD, JF
    FALK, JE
    [J]. COMPUTERS & OPERATIONS RESEARCH, 1982, 9 (02) : 153 - 159
  • [5] Bazaraa M.S., 2013, NONLINEAR PROGRAMMIN
  • [6] Partitioning procedures for solving mixed-variables programming problems
    Benders, J. F.
    [J]. COMPUTATIONAL MANAGEMENT SCIENCE, 2005, 2 (01) : 3 - 19
  • [7] INFORMATION-THEORY, DISTANCE MATRIX, AND MOLECULAR BRANCHING
    BONCHEV, D
    TRINAJSTIC, N
    [J]. JOURNAL OF CHEMICAL PHYSICS, 1977, 67 (10) : 4517 - 4533
  • [8] Optimization in polymer design using connectivity indices
    Camarda, KV
    Maranas, CD
    [J]. INDUSTRIAL & ENGINEERING CHEMISTRY RESEARCH, 1999, 38 (05) : 1884 - 1892
  • [9] Charnes A., 1954, NAVAL RES LOGISTICS, V1, P301
  • [10] Danon L., 2011, Interdisciplinary Perspectives on Infectious Diseases, V2011, P284909, DOI 10.1155/2011/284909