DROPS

Artifact

Software

HeiOrient

Authors: Henrik Reinstädtler, Christian Schulz, and Bora Uçar

Abstract

Cite as

Henrik Reinstädtler, Christian Schulz, Bora Uçar. HeiOrient (Software, Source Code). Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@misc{dagstuhl-artifact-22501,
   title = {{HeiOrient}}, 
   author = {Reinst\"{a}dtler, Henrik and Schulz, Christian and U\c{c}ar, Bora},
   note = {Software, DFG-SCHU 2567/3-1, swhId: \href{https://archive.softwareheritage.org/swh:1:dir:be7317d125554a54dfd1c9d17521c500c4e1ebc3;origin=https://github.com/HeiOrient/HeiOrient;visit=swh:1:snp:ad428689c405e27808a6eac12433782b1de2166e;anchor=swh:1:rev:830c983f61d5199a6b6b0daab77fddf55d158cfd}{\texttt{swh:1:dir:be7317d125554a54dfd1c9d17521c500c4e1ebc3}} (visited on 2024-11-28)},
   url = {https://github.com/HeiOrient/HeiOrient},
   doi = {10.4230/artifacts.22501},
}

Document

DOI: 10.4230/LIPIcs.ESA.2024.97

Engineering Edge Orientation Algorithms

Authors: Henrik Reinstädtler, Christian Schulz, and Bora Uçar

Published in: LIPIcs, Volume 308, 32nd Annual European Symposium on Algorithms (ESA 2024)

Abstract

Given an undirected graph G, the edge orientation problem asks for assigning a direction to each edge to convert G into a directed graph. The aim is to minimize the maximum out-degree of a vertex in the resulting directed graph. This problem, which is solvable in polynomial time, arises in many applications. An ongoing challenge in edge orientation algorithms is their scalability, particularly in handling large-scale networks with millions or billions of edges efficiently. We propose a novel algorithmic framework based on finding and manipulating simple paths to face this challenge. Our framework is based on an existing algorithm and allows many algorithmic choices. By carefully exploring these choices and engineering the underlying algorithms, we obtain an implementation which is more efficient and scalable than the current state-of-the-art. Our experiments demonstrate significant performance improvements compared to state-of-the-art solvers. On average our algorithm is 6.59 times faster when compared to the state-of-the-art.

Cite as

Henrik Reinstädtler, Christian Schulz, and Bora Uçar. Engineering Edge Orientation Algorithms. In 32nd Annual European Symposium on Algorithms (ESA 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 308, pp. 97:1-97:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{reinstadtler_et_al:LIPIcs.ESA.2024.97,
  author =	{Reinst\"{a}dtler, Henrik and Schulz, Christian and U\c{c}ar, Bora},
  title =	{{Engineering Edge Orientation Algorithms}},
  booktitle =	{32nd Annual European Symposium on Algorithms (ESA 2024)},
  pages =	{97:1--97:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-338-6},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{308},
  editor =	{Chan, Timothy and Fischer, Johannes and Iacono, John 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.2024.97},
  URN =		{urn:nbn:de:0030-drops-211682},
  doi =		{10.4230/LIPIcs.ESA.2024.97},
  annote =	{Keywords: edge orientation, pseudoarboricity, graph algorithms}
}

Search Results

Documents authored by Reinstädtler, Henrik

HeiOrient

Abstract

Cite as

Engineering Edge Orientation Algorithms

Abstract

Cite as

Thanks for your feedback!

Could not send message