This article addresses the 2-edge-connected minimum branch vertices problem, a variant of the minimum branch vertices problem in which the spanning subgraph is required to be 2-edge-connected for survivability reasons. The problem has been recently introduced and finds application in optical networks design scenarios, where branch vertices are associated to switch devices that allow to split the entering light signals and send them to several adjacent vertices. An exact approach to the problem has been proposed in the literature. In this paper, we formally prove its NP-completeness and propose a genetic algorithm, which exploits some literature-provided procedures for efficiently checking and restoring solutions feasibility, and makes use of novel ad-hoc designed operators aiming to improve their values, reducing the number of branch vertices. The computational tests show that, on the benchmark instances, the genetic algorithm very often finds the optimal solution. Moreover, in order to further investigate the effectiveness and the performance of our algorithm, we generated a new set of random instances where the optimal solution is known a priori.

A genetic approach for the 2-edge-connected minimum branch vertices problem

Carrabs F.;Cerulli R.;Laureana F.;Serra D.
;
Sorgente C.
2023-01-01

Abstract

This article addresses the 2-edge-connected minimum branch vertices problem, a variant of the minimum branch vertices problem in which the spanning subgraph is required to be 2-edge-connected for survivability reasons. The problem has been recently introduced and finds application in optical networks design scenarios, where branch vertices are associated to switch devices that allow to split the entering light signals and send them to several adjacent vertices. An exact approach to the problem has been proposed in the literature. In this paper, we formally prove its NP-completeness and propose a genetic algorithm, which exploits some literature-provided procedures for efficiently checking and restoring solutions feasibility, and makes use of novel ad-hoc designed operators aiming to improve their values, reducing the number of branch vertices. The computational tests show that, on the benchmark instances, the genetic algorithm very often finds the optimal solution. Moreover, in order to further investigate the effectiveness and the performance of our algorithm, we generated a new set of random instances where the optimal solution is known a priori.
2023
File in questo prodotto:
Non ci sono file associati a questo prodotto.

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/11386/4816555
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 0
  • ???jsp.display-item.citation.isi??? 0
social impact