The Weighted Safe Set Problem aims to determine in an undirected graph a subset of vertices such that the weights of the connected components they induce exceed the weights of the adjacent components induced by the complementary subset. We tackle the problem with various approaches based on randomised constructive and destructive procedures, comparing them with each other and with the only other existing heuristic approach, that is a randomised destructive heuristic. The experiments concern all the available benchmark instances (random graphs up to 60 vertices), but also new benchmark instances with larger size and different topologies, namely random, small-world, regular, planar, grid and real-world graphs up to 300 vertices. Dense random graphs, in fact, appear to become progressively easier to solve as their size grows. On the other instances, the best performance is obtained by combining a randomised constructive procedure, a deterministic destructive procedure, and delayed termination conditions that allow a deeper exploration of the feasible region.

Constructive–destructive heuristics for the Safe Set Problem

Hosteins P.
2023-01-01

Abstract

The Weighted Safe Set Problem aims to determine in an undirected graph a subset of vertices such that the weights of the connected components they induce exceed the weights of the adjacent components induced by the complementary subset. We tackle the problem with various approaches based on randomised constructive and destructive procedures, comparing them with each other and with the only other existing heuristic approach, that is a randomised destructive heuristic. The experiments concern all the available benchmark instances (random graphs up to 60 vertices), but also new benchmark instances with larger size and different topologies, namely random, small-world, regular, planar, grid and real-world graphs up to 300 vertices. Dense random graphs, in fact, appear to become progressively easier to solve as their size grows. On the other instances, the best performance is obtained by combining a randomised constructive procedure, a deterministic destructive procedure, and delayed termination conditions that allow a deeper exploration of the feasible region.
2023
159
1
13
https://www-sciencedirect-com.bibliopass.unito.it/science/article/pii/S0305054823001752
Graph partitioning; Safe Set Problem; Greedy Randomized Adaptive Search; Procedure; Large Neighbourhood Search
Boggio Tomasaz A.; Cordone R.; Hosteins P.
File in questo prodotto:
File Dimensione Formato  
Safe_Set_Heuristics_Paper.pdf

Accesso aperto

Tipo di file: POSTPRINT (VERSIONE FINALE DELL’AUTORE)
Dimensione 403.9 kB
Formato Adobe PDF
403.9 kB Adobe PDF Visualizza/Apri
1-s2.0-S0305054823001752-main.pdf

Accesso aperto

Descrizione: articolo editoriale
Tipo di file: PDF EDITORIALE
Dimensione 729.24 kB
Formato Adobe PDF
729.24 kB Adobe PDF Visualizza/Apri

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/2318/1950593
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 4
  • ???jsp.display-item.citation.isi??? 3
social impact