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.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.