The Weighted Safe Set Problem requires to partition an undirected graph into two families of connected components, respectively denoted as safe and unsafe, in such a way that each safe component dominates the unsafe adjacent components with respect to a weight function. We introduce a combinatorial branch and bound approach, whose main strength is a refined relaxation that combines graph manipulations and the solution of an auxiliary problem. We also propose fixing procedures to reduce the number of branching nodes. The algorithm solves all weighted instances available in the literature and most unweighted ones, up to 50 vertices, with computational times orders of magnitude smaller than the competing algorithms. In order to investigate the limits of the approach, we introduce a benchmark of graphs with 60 vertices, solving to optimality the denser instances.

A combinatorial branch and bound for the safe set problem / A. BOGGIO TOMASAZ, R. Cordone, P. Hosteins. - In: NETWORKS. - ISSN 1097-0037. - 81:4(2023 Jun), pp. 445-464. [10.1002/net.22140]

### A combinatorial branch and bound for the safe set problem

#### Abstract

The Weighted Safe Set Problem requires to partition an undirected graph into two families of connected components, respectively denoted as safe and unsafe, in such a way that each safe component dominates the unsafe adjacent components with respect to a weight function. We introduce a combinatorial branch and bound approach, whose main strength is a refined relaxation that combines graph manipulations and the solution of an auxiliary problem. We also propose fixing procedures to reduce the number of branching nodes. The algorithm solves all weighted instances available in the literature and most unweighted ones, up to 50 vertices, with computational times orders of magnitude smaller than the competing algorithms. In order to investigate the limits of the approach, we introduce a benchmark of graphs with 60 vertices, solving to optimality the denser instances.
##### Scheda breve Scheda completa Scheda completa (DC)
branch and bound; graph partitioning; safe set;
Settore INF/01 - Informatica
Settore MAT/09 - Ricerca Operativa
giu-2023
23-dic-2022
Article (author)
File in questo prodotto:
File
Networks - 2022 - Boggio Tomasaz - A combinatorial branch and bound for the safe set problem.pdf

accesso riservato

Descrizione: Research Article
Tipologia: Publisher's version/PDF
Dimensione 1.85 MB
Formato Adobe PDF
safe set beb 5 dicembre.pdf

Open Access dal 02/07/2024

Tipologia: Post-print, accepted manuscript ecc. (versione accettata dall'editore)
Dimensione 502.4 kB
Formato Adobe PDF
##### Pubblicazioni consigliate

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/2434/967805`
• ND
• 3
• 2