| Issue |
RAIRO-Oper. Res.
Volume 57, Number 1, January-February 2023
|
|
|---|---|---|
| Page(s) | 87 - 97 | |
| DOI | https://doi.org/10.1051/ro/2022215 | |
| Published online | 12 January 2023 | |
The widest k-set of disjoint paths problem
1
Computer Science Department, Universidade Federal de Minas Gerais, Av. Pres. Antônio Carlos 6627, Belo Horizonte, MG 31270-901, Brazil
2
Computer Science Department, Universidade Federal de Alfenas, Av. Jovino Fernandes de Sales 2600, Alfenas, MG 37133-840, Brazil
* Corresponding author: iago.august@gmail.com; iago.carvalho@unifal-mg.edu.br
Received:
25
July
2022
Accepted:
18
December
2022
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.
Mathematics Subject Classification: 68R01 / 90C11 / 90C17 / 90C47 / 90C59
Key words: Widest paths / disjoint paths / network flows / integer programming / heuristics
© The authors. Published by EDP Sciences, ROADEF, SMAI 2023
This is an Open Access article distributed under the terms of the Creative Commons Attribution License (https://creativecommons.org/licenses/by/4.0), which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.
Current usage metrics show cumulative count of Article Views (full-text article views including HTML views, PDF and ePub downloads, according to the available data) and Abstracts Views on Vision4Press platform.
Data correspond to usage on the plateform after 2015. The current usage metrics is available 48-96 hours after online publication and is updated daily on week days.
Initial download of the metrics may take a while.