463. On Satisfying Connectivity Requirements In Digraphs With Arc Operations
Invited abstract in session MD-20: Problems on graphs, stream Combinatorial Optimization.
Monday, 14:30-16:00Room: Esther Simpson 2.11
Authors (first author is the speaker)
| 1. | Matheus Corrêa
|
| Instituto Alberto Luiz Coimbra de Pós-Graduação e Pesquisa em Engenharia, Universidade Federal do Rio de Janeiro | |
| 2. | Abilio Lucena
|
| Systems Engineering and Computer Science - COPPE, Federal University of Rio de Janeiro |
Abstract
Let D = (V, A) be a directed graph. In many applications, D may lack a desired connectivity property, such as strong connectivity. To address this issue, a single arc operation—such as addition or reversal—can be repeatedly applied to transform D into a digraph D’ = (V, A’) that satisfies the required connectivity. In this study, we explore various problems that involve modifying a digraph using arc operations to achieve specific connectivity properties. Most of these problems are NP-hard. Consequently, we develop exact algorithms based on well-known optimization techniques, including Branch-and-Cut and Lagrangian Relaxation. Our results indicate that, when used individually, these techniques yield limited success. However, when combined, they enable us to solve all tested instances effectively.
Keywords
- Graphs and Networks
- Combinatorial Optimization
- Algorithms
Status: accepted
Back to the list of papers