2 Search Results for "Bertram, Nico"

Document
DOI: 10.4230/LIPIcs.SEA.2022.10
A Parallel Framework for Approximate Max-Dicut in Partitionable Graphs

Authors: Nico Bertram, Jonas Ellert, and Johannes Fischer

Published in: LIPIcs, Volume 233, 20th International Symposium on Experimental Algorithms (SEA 2022)

Abstract
Computing a maximum cut in undirected and weighted graphs is a well studied problem and has many practical solutions that also scale well in shared memory (despite its NP-completeness). For its counterpart in directed graphs, however, we are not aware of practical solutions that also utilize parallelism. We engineer a framework that computes a high quality approximate cut in directed and weighted graphs by using a graph partitioning approach. The general idea is to partition a graph into k subgraphs using a parallel partitioning algorithm of our choice (the first ingredient of our framework). Then, for each subgraph in parallel, we compute a cut using any polynomial time approximation algorithm (the second ingredient). In a final step, we merge the locally computed solutions using a high-quality or exact parallel Max-Dicut algorithm (the third ingredient). On graphs that can be partitioned well, the quality of the computed cut is significantly better than the best cut achieved by any linear time algorithm. This is particularly relevant for large graphs, where linear time algorithms used to be the only feasible option.
Cite as

Nico Bertram, Jonas Ellert, and Johannes Fischer. A Parallel Framework for Approximate Max-Dicut in Partitionable Graphs. In 20th International Symposium on Experimental Algorithms (SEA 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 233, pp. 10:1-10:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{bertram_et_al:LIPIcs.SEA.2022.10,
  author =	{Bertram, Nico and Ellert, Jonas and Fischer, Johannes},
  title =	{{A Parallel Framework for Approximate Max-Dicut in Partitionable Graphs}},
  booktitle =	{20th International Symposium on Experimental Algorithms (SEA 2022)},
  pages =	{10:1--10:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-251-8},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{233},
  editor =	{Schulz, Christian and U\c{c}ar, Bora},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2022.10},
  URN =		{urn:nbn:de:0030-drops-165441},
  doi =		{10.4230/LIPIcs.SEA.2022.10},
  annote =	{Keywords: maximum directed cut, graph partitioning, algorithm engineering, approximation, parallel algorithms}
}
Document
DOI: 10.4230/LIPIcs.ESA.2021.15
Lyndon Words Accelerate Suffix Sorting

Authors: Nico Bertram, Jonas Ellert, and Johannes Fischer

Published in: LIPIcs, Volume 204, 29th Annual European Symposium on Algorithms (ESA 2021)

Abstract
Suffix sorting is arguably the most fundamental building block in string algorithmics, like regular sorting in the broader field of algorithms. It is thus not surprising that the literature is full of algorithms for suffix sorting, in particular focusing on their practicality. However, the advances on practical suffix sorting stalled with the emergence of the DivSufSort algorithm more than 10 years ago, which, up to date, has remained the fastest suffix sorter. This article shows how properties of Lyndon words can be exploited algorithmically to accelerate suffix sorting again. Our new algorithm is 6-19% faster than DivSufSort on real-world texts, and up to three times as fast on artificial repetitive texts. It can also be parallelized, where similar speedups can be observed. Thus, we make the first advances in practical suffix sorting after more than a decade of standstill.
Cite as

Nico Bertram, Jonas Ellert, and Johannes Fischer. Lyndon Words Accelerate Suffix Sorting. In 29th Annual European Symposium on Algorithms (ESA 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 204, pp. 15:1-15:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{bertram_et_al:LIPIcs.ESA.2021.15,
  author =	{Bertram, Nico and Ellert, Jonas and Fischer, Johannes},
  title =	{{Lyndon Words Accelerate Suffix Sorting}},
  booktitle =	{29th Annual European Symposium on Algorithms (ESA 2021)},
  pages =	{15:1--15:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-204-4},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{204},
  editor =	{Mutzel, Petra and Pagh, Rasmus and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2021.15},
  URN =		{urn:nbn:de:0030-drops-145961},
  doi =		{10.4230/LIPIcs.ESA.2021.15},
  annote =	{Keywords: Suffix array, suffix sorting, Lyndon words, string algorithms}
}
  • Refine by Author
  • 2 Bertram, Nico
  • 2 Ellert, Jonas
  • 2 Fischer, Johannes

  • Refine by Classification
  • 2 Theory of computation → Design and analysis of algorithms
  • 1 Mathematics of computing → Graph algorithms

  • Refine by Keyword
  • 1 Lyndon words
  • 1 Suffix array
  • 1 algorithm engineering
  • 1 approximation
  • 1 graph partitioning
  • Show More...

  • Refine by Type
  • 2 document

  • Refine by Publication Year
  • 1 2021
  • 1 2022

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

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