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 条
  • [41] Gamma deployment problem in grids: hardness and new integer linear programming formulation
    Faraj, Marcelo Fonseca
    Urrutia, Sebastian
    Sarubbi, Joao F. M.
    INTERNATIONAL TRANSACTIONS IN OPERATIONAL RESEARCH, 2020, 27 (06) : 2740 - 2759
  • [42] Comparison of Some Cutting-Plane Methods for the Integer Linear Programming Problem
    Shalbuzov K.D.
    Computational Mathematics and Modeling, 2015, 26 (2) : 244 - 251
  • [43] A method to improve integer linear programming problem with branch-and-bound procedure
    Chan, Din-Yuen
    Ku, Cheng-Yuan
    Li, Ming-Chai
    APPLIED MATHEMATICS AND COMPUTATION, 2006, 179 (02) : 484 - 493
  • [44] A Mixed-Integer Linear Programming Model for a Selective Vehicle Routing Problem
    Posada, Andrea
    Carlos Rivera, Juan
    Palacio, Juan D.
    APPLIED COMPUTER SCIENCES IN ENGINEERING, WEA 2018, PT II, 2018, 916 : 108 - 119
  • [45] On the Quasistability Radius for a Multicriteria Integer Linear Programming Problem of Finding Extremum Solutions
    V. Emelichev
    Yu. Nikulin
    Cybernetics and Systems Analysis, 2019, 55 : 949 - 957
  • [46] AN INTEGER LINEAR PROGRAMMING MODEL FOR THE THREE-DIMENSIONAL MARBLE CUTTING PROBLEM
    Yilmaz, Gokhan
    Sahin, Yusuf
    JOURNAL OF MEHMET AKIF ERSOY UNIVERSITY ECONOMICS AND ADMINISTRATIVE SCIENCES FACULTY, 2023, 10 (01): : 658 - 669
  • [47] A surface-based DNA computing for the positive integer linear programming problem
    Yin, Zhi-xiang
    Cui, Jian-zhong
    Yang, Jin
    ADVANCED INTELLIGENT COMPUTING THEORIES AND APPLICATIONS: WITH ASPECTS OF THEORETICAL AND METHODOLOGICAL ISSUES, 2007, 4681 : 1 - +
  • [48] On a type of stability of a multicriteria integer linear programming problem in the case of a monotone norm
    V. A. Emelichev
    K. G. Kuz’min
    Journal of Computer and Systems Sciences International, 2007, 46 : 714 - 720
  • [49] Integer Linear Programming for the Tutor Allocation Problem: A practical case in a British University
    Caselli, Giulia
    Delorme, Maxence
    Iori, Manuel
    EXPERT SYSTEMS WITH APPLICATIONS, 2022, 187
  • [50] On a type of stability of a multicriteria integer linear programming problem in the case of a monotone norm
    Emelichev, V. A.
    Kuz'min, K. G.
    JOURNAL OF COMPUTER AND SYSTEMS SCIENCES INTERNATIONAL, 2007, 46 (05) : 714 - 720
12345