.png){kind=icon}
.png){kind=icon}
Return
A new formulation for the Safe Set problem on graphs
.png){kind=icon}
PRE
AI
DOI：10.1016/j.cor.2019.07.004.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
Let G = (V, E) be a finite simple connected graph and S be a non-empty subset of V, the subgraph of G induced by the subset S is denoted by G[S]. Consider the function w, which assigns a positive real number as a weight to each vertex belonging to V and for a subset S of V, let w(S) be the sum of all weights of the vertices belonging to S. A subset S of V is a weighted Safe Set if, for any maximal component C of G[S], w(C) is greater or equal than w(D) for every maximal component D of G[V \ S] connected to C. A maximal component C of G[S] is a subset of vertices in which all its adjacent vertices do not belong to S. If every vertex belonging to V has a weight equal to one, the non-empty subset S of V is called a Safe Set. Furthermore, if G[S] is connected, it characterizes a Connected Safe Set. The optimal solution of the Safe Set Problem is a subset S which minimizes w(S). This work presents a mixed integer linear programming formulation and a Branch and Cut algorithm for both the Weighted Safe Set and the Safe Set problems. In addition, for the Safe Set problem, a pre-processing test is suggested. This work also contributes with a heuristic procedure for the Weighted Safe Set and the Safe Set problems. Computational experiments showed the efficiency of each of the proposed methods. (C) 2019 Elsevier Ltd. All rights reserved.
Keywords:
Safe set problem
Branch-and-cut algorithm
Heuristic
AI Summary
Key information extracted from the uploaded paper, including a brief overview, abstract, background, key highlights, visual analysis, and future outlook.
Journal
C
IF:
4.3
Papers:
6.5K
Citations:
1.8W