Engineering Fully Dynamic Exact $Δ$-Orientation Algorithms
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2024
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866909259843764224 |
|---|---|
| author | Großmann, Ernestine Reinstädtler, Henrik Schulz, Christian Walliser, Fabian |
| author_facet | Großmann, Ernestine Reinstädtler, Henrik Schulz, Christian Walliser, Fabian |
| contents | A (fully) dynamic graph algorithm is a data structure that supports edge insertions, edge deletions, and answers specific queries pertinent to the problem at hand. In this work, we address the fully dynamic edge orientation problem, also known as the fully dynamic $Δ$-orientation problem. The objective is to maintain an orientation of the edges in an undirected graph such that the out-degree of any vertex remains low. When edges are inserted or deleted, it may be necessary to reorient some edges to prevent vertices from having excessively high out-degrees. In this paper, we introduce the first algorithm that maintains an optimal edge orientation during both insertions and deletions. In experiments comparing with recent nearly exact algorithms, we achieve a 32% lower running time. The update time of our algorithm is up to 6 orders of magnitude faster than static exact algorithms. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2407_12595 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Engineering Fully Dynamic Exact $Δ$-Orientation Algorithms Großmann, Ernestine Reinstädtler, Henrik Schulz, Christian Walliser, Fabian Data Structures and Algorithms A (fully) dynamic graph algorithm is a data structure that supports edge insertions, edge deletions, and answers specific queries pertinent to the problem at hand. In this work, we address the fully dynamic edge orientation problem, also known as the fully dynamic $Δ$-orientation problem. The objective is to maintain an orientation of the edges in an undirected graph such that the out-degree of any vertex remains low. When edges are inserted or deleted, it may be necessary to reorient some edges to prevent vertices from having excessively high out-degrees. In this paper, we introduce the first algorithm that maintains an optimal edge orientation during both insertions and deletions. In experiments comparing with recent nearly exact algorithms, we achieve a 32% lower running time. The update time of our algorithm is up to 6 orders of magnitude faster than static exact algorithms. |
| title | Engineering Fully Dynamic Exact $Δ$-Orientation Algorithms |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2407.12595 |