1879. Graph Sparsification to Preserve Connectivity: a GRASP approach
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. | Claude PETIT
|
| Lab-STICC, UMR 6285, CNRS, Université Bretagne Sud | |
| 2. | Alexandru Olteanu
|
| Lab-STICC, UMR 6285, CNRS, Université Bretagne Sud | |
| 3. | Quentin Perrachon
|
| Lab-STICC, UMR 6285, CNRS, Université Bretagne Sud | |
| 4. | Marc Sevaux
|
| Lab-STICC, UMR 6285, CNRS, Université Bretagne Sud |
Abstract
Sparsifying a graph helps accelerate algorithms that involve any type of computation on its edges. However, this operation alters the properties of the graph, even though it might be important to preserve them. Therefore, it is crucial to have sparsification algorithms that guarantee the maintenance or minimal degradation of certain properties of the original graph.
In this work, we propose to study two greedy graph sparsification algorithms to maximize connectivity for a given number of edges. The original algorithms are deterministic and have a complexity of O(nk) and O(k(n+k)) respectively, where n is the number of nodes and k is the number of edges of the sparsified graph. The variants are inspired by the GRASP metaheuristic, and studying their performance shed light on both the optimality of the original algorithms and potential areas for improvement.
Graph sparsification counts numerous applications, such as in transportation problems or in applications involving Graph Neural Networks (GNNs).
Keywords
- Metaheuristics
- Graphs and Networks
Status: accepted
Back to the list of papers