Integer linear programming models for the weighted total domination problem

被引：16
|
作者：
Ma, Yuede [1 ]
Cai, Qingqiong [2 ]
Yao, Shunyu [3 ,4 ]
机构：
[1] Xian Technol Univ, Sch Sci, Xian 710021, Shanxi, Peoples R China
[2] Nankai Univ, Coll Comp Sci, Tianjin 300350, Peoples R China
[3] Nankai Univ, Ctr Combinator, Tianjin 300071, Peoples R China
[4] Nankai Univ, LPMC, Tianjin 300071, Peoples R China
来源：
APPLIED MATHEMATICS AND COMPUTATION | 2019年 / 358卷
基金：
中国国家自然科学基金;
关键词：
Weighted total domination; Integer linear programming; Combinatorial optimization; Graph theory; INDEPENDENT DOMINATION;
D O I：
10.1016/j.amc.2019.04.038
中图分类号：
O29 [应用数学];
学科分类号：
070104 ;
摘要：
A total dominating set of a graph G = (V, E) is a subset D of V such that every vertex in V (including the vertices from D) has at least one neighbour in D. Suppose that every vertex v is an element of V has an integer weight w(v) >= 0 and every edge e is an element of E has an integer weight w(e) >= 0. Then the weighted total domination (WTD) problem is to find a total dominating set D which minimizes the cost f (D) := Sigma(u is an element of D )w(u) + Sigma(e is an element of E[D]) w(e) + Sigma(v is an element of V\D) min{w(uv) vertical bar u is an element of N(v) boolean AND D}. In this paper, we put forward three integer linear programming (ILP) models with a polynomial number of constraints, and present some numerical results implemented on random graphs for WTD problem. (C) 2019 Elsevier Inc. All rights reserved.
引用
收藏
页码：146 / 150
页数：5
相关论文
共 50 条
  • [21] Computational performance evaluation of two integer linear programming models for the minimum common string partition problem
    Christian Blum
    Günther R. Raidl
    Optimization Letters, 2016, 10 : 189 - 205
  • [22] Integer programming models for the multidimensional assignment problem with star costs
    Walteros, Jose L.
    Vogiatzis, Chrysafis
    Pasiliao, Eduardo L.
    Pardalos, Panos M.
    EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2014, 235 (03) : 553 - 568
  • [23] Integer programming models and linearizations for the traveling car renter problem
    Marco C. Goldbarg
    Elizabeth F. G. Goldbarg
    Henrique P. L. Luna
    Matheus S. Menezes
    Lucas Corrales
    Optimization Letters, 2018, 12 : 743 - 761
  • [24] Integer linear programming model for multidimensional two-way number partitioning problem
    Kojic, Jelena
    COMPUTERS & MATHEMATICS WITH APPLICATIONS, 2010, 60 (08) : 2302 - 2308
  • [25] Integer programming models and linearizations for the traveling car renter problem
    Goldbarg, Marco C.
    Goldbarg, Elizabeth F. G.
    Luna, Henrique P. L.
    Menezes, Matheus S.
    Corrales, Lucas
    OPTIMIZATION LETTERS, 2018, 12 (04) : 743 - 761
  • [26] An Integer Linear Programming Model for Solving Radio Mean Labeling Problem
    Badr, Elsayed
    Almotairi, Sultan
    Eirokh, Ashraf
    Abdel-Hay, Atef
    Almutairi, Badr
    IEEE ACCESS, 2020, 8 : 162343 - 162349
  • [27] A mixed integer linear programming formulation for the vehicle routing problem with backhauls
    Granada-Echeverri, Mauricio
    Toro, Eliana M.
    Santa, Jhon Jairo
    INTERNATIONAL JOURNAL OF INDUSTRIAL ENGINEERING COMPUTATIONS, 2019, 10 (02) : 295 - 308
  • [28] Solving the Join Ordering Problem via Mixed Integer Linear Programming
    Trummer, Immanuel
    Koch, Christoph
    SIGMOD'17: PROCEEDINGS OF THE 2017 ACM INTERNATIONAL CONFERENCE ON MANAGEMENT OF DATA, 2017, : 1025 - 1040
  • [29] SOLVING THE SENSOR COVER ENERGY PROBLEM VIA INTEGER LINEAR PROGRAMMING
    Li, Pingke
    KYBERNETIKA, 2021, 57 (04) : 568 - 593
  • [30] A NEW MIXED INTEGER LINEAR PROGRAMMING FORMULATION FOR THE MAXIMUM DEGREE BOUNDED CONNECTED SUBGRAPH PROBLEM
    Maksimovic, Zoran
    PUBLICATIONS DE L INSTITUT MATHEMATIQUE-BEOGRAD, 2016, 99 (113): : 99 - 108
12345