E-resources
Peer reviewed
Open access
-
Ribeiro, Marco Antônio; Carvalho, Iago Augusto; Pereira, Armando Honório
R.A.I.R.O. Recherche opérationnelle, 01/2023, Volume: 57, Issue: 1Journal Article
Finding disjoint and widest paths are key problems in telecommunication networks. In this paper, we study the Widest k -set of Disjoint Paths Problem (WKDPP), an NP -Hard optimization problem that considers both aspects. Given a digraph G = ( N , A ), WKDPP consists of computing k arc-disjoint paths between two nodes such that the sum of its minimum capacity arcs is maximized. We present three mathematical formulations for WKDPP, a symmetry-breaking inequality set, and propose two heuristic algorithms. Computational experiments compare the proposed heuristics with another from the literature to show the effectiveness of the proposed methods.
