Search Results

Documents authored by Vlieghe, Juliette

Artifact
Software
DOI: 10.4230/artifacts.24670
Implementation of our dynamic algorithm for minimum orientation

Authors: Ernestine Grossmann, Henrik Reinstädtler, Eva Rotenberg, Christian Schulz, Ivor van der Hoog, and Juliette Vlieghe

Abstract
Cite as

Ernestine Grossmann, Henrik Reinstädtler, Eva Rotenberg, Christian Schulz, Ivor van der Hoog, Juliette Vlieghe. Implementation of our dynamic algorithm for minimum orientation (Software, Source Code). Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@misc{dagstuhl-artifact-24670,
   title = {{Implementation of our dynamic algorithm for minimum orientation}}, 
   author = {Grossmann, Ernestine and Reinst\"{a}dtler, Henrik and Rotenberg, Eva and Schulz, Christian and van der Hoog, Ivor and Vlieghe, Juliette},
   note = {Software, Villum Fonden VIL37507, DFG SCHU 2567/8-1, Marie Skłodowska-Curie 899987, swhId: \href{https://archive.softwareheritage.org/swh:1:dir:0ea52feafca9f6d8ce3ee893686fde2510513e9e;origin=https://github.com/DynGraphLab/DynDeltaApprox;visit=swh:1:snp:d75d11daa88538aaa86297daef487996502d243b;anchor=swh:1:rev:f8c3028a966664ce26b0f32c08de00dec2103127}{\texttt{swh:1:dir:0ea52feafca9f6d8ce3ee893686fde2510513e9e}} (visited on 2025-10-01)},
   url = {https://github.com/DynGraphLab/DynDeltaApprox},
   doi = {10.4230/artifacts.24670},
}
Document
DOI: 10.4230/LIPIcs.ESA.2025.65
From Theory to Practice: Engineering Approximation Algorithms for Dynamic Orientation

Authors: Ernestine Grossmann, Henrik Reinstädtler, Eva Rotenberg, Christian Schulz, Ivor van der Hoog, and Juliette Vlieghe

Published in: LIPIcs, Volume 351, 33rd Annual European Symposium on Algorithms (ESA 2025)

Abstract
Dynamic graph algorithms have seen significant theoretical advancements, but practical evaluations often lag behind. This work bridges the gap between theory and practice by engineering and empirically evaluating recently developed approximation algorithms for dynamically maintaining graph orientations. We comprehensively describe the underlying data structures, including efficient bucketing techniques and round-robin updates. Our implementation has a natural parameter λ, which allows for a trade-off between algorithmic efficiency and the quality of the solution. In the extensive experimental evaluation, we demonstrate that our implementation offers a considerable speedup. Using different quality metrics, we show that our implementations are very competitive and can outperform previous methods. Overall, our approach solves more instances than other methods while being up to 112 times faster on instances that are solvable by all methods compared.
Cite as

Ernestine Grossmann, Henrik Reinstädtler, Eva Rotenberg, Christian Schulz, Ivor van der Hoog, and Juliette Vlieghe. From Theory to Practice: Engineering Approximation Algorithms for Dynamic Orientation. In 33rd Annual European Symposium on Algorithms (ESA 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 351, pp. 65:1-65:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{grossmann_et_al:LIPIcs.ESA.2025.65,
  author =	{Grossmann, Ernestine and Reinst\"{a}dtler, Henrik and Rotenberg, Eva and Schulz, Christian and van der Hoog, Ivor and Vlieghe, Juliette},
  title =	{{From Theory to Practice: Engineering Approximation Algorithms for Dynamic Orientation}},
  booktitle =	{33rd Annual European Symposium on Algorithms (ESA 2025)},
  pages =	{65:1--65:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-395-9},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{351},
  editor =	{Benoit, Anne and Kaplan, Haim and Wild, Sebastian and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2025.65},
  URN =		{urn:nbn:de:0030-drops-245331},
  doi =		{10.4230/LIPIcs.ESA.2025.65},
  annote =	{Keywords: Dynamic graphs, out-orientation}
}
Document
DOI: 10.4230/LIPIcs.SWAT.2024.20
Sparsity-Parameterised Dynamic Edge Colouring

Authors: Aleksander B. G. Christiansen, Eva Rotenberg, and Juliette Vlieghe

Published in: LIPIcs, Volume 294, 19th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2024)

Abstract
We study the edge-colouring problem, and give efficient algorithms where the number of colours is parameterised by the graph’s arboricity, α. In a dynamic graph, subject to insertions and deletions, we give a deterministic algorithm that updates a proper Δ + O(α) edge colouring in poly(log n) amortized time. Our algorithm is fully adaptive to the current value of the maximum degree and arboricity. In this fully-dynamic setting, the state-of-the-art edge-colouring algorithms are either a randomised algorithm using (1 + ε)Δ colours in poly(log n, ε^{-1}) time per update, or the naive greedy algorithm which is a deterministic 2Δ -1 edge colouring with log(Δ) update time. Compared to the (1+ε)Δ algorithm, our algorithm is deterministic and asymptotically faster, and when α is sufficiently small compared to Δ, it even uses fewer colours. In particular, ours is the first Δ+O(1) edge-colouring algorithm for dynamic forests, and dynamic planar graphs, with polylogarithmic update time. Additionally, in the static setting, we show that we can find a proper edge colouring with Δ + 2α colours in O(mlog n) time. Moreover, the colouring returned by our algorithm has the following local property: every edge uv is coloured with a colour in {1, max{deg(u), deg(v)} + 2α}. The time bound matches that of the greedy algorithm that computes a 2Δ-1 colouring of the graph’s edges, and improves the number of colours when α is sufficiently small compared to Δ.
Cite as

Aleksander B. G. Christiansen, Eva Rotenberg, and Juliette Vlieghe. Sparsity-Parameterised Dynamic Edge Colouring. In 19th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 294, pp. 20:1-20:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{christiansen_et_al:LIPIcs.SWAT.2024.20,
  author =	{Christiansen, Aleksander B. G. and Rotenberg, Eva and Vlieghe, Juliette},
  title =	{{Sparsity-Parameterised Dynamic Edge Colouring}},
  booktitle =	{19th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2024)},
  pages =	{20:1--20:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-318-8},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{294},
  editor =	{Bodlaender, Hans L.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2024.20},
  URN =		{urn:nbn:de:0030-drops-200608},
  doi =		{10.4230/LIPIcs.SWAT.2024.20},
  annote =	{Keywords: edge colouring, arboricity, hierarchical partition, dynamic algorithms, amortized analysis}
}
Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact