17 Search Results for "Stølting Brodal, Gerth"

Document
DOI: 10.4230/LIPIcs.SEA.2024.6
Faster Treewidth-Based Approximations for Wiener Index

Authors: Giovanna Kobus Conrado, Amir Kafshdar Goharshady, Pavel Hudec, Pingjiang Li, and Harshit Jitendra Motwani

Published in: LIPIcs, Volume 301, 22nd International Symposium on Experimental Algorithms (SEA 2024)

Abstract
The Wiener index of a graph G is the sum of distances between all pairs of its vertices. It is a widely-used graph property in chemistry, initially introduced to examine the link between boiling points and structural properties of alkanes, which later found notable applications in drug design. Thus, computing or approximating the Wiener index of molecular graphs, i.e. graphs in which every vertex models an atom of a molecule and every edge models a bond, is of significant interest to the computational chemistry community. In this work, we build upon the observation that molecular graphs are sparse and tree-like and focus on developing efficient algorithms parameterized by treewidth to approximate the Wiener index. We present a new randomized approximation algorithm using a combination of tree decompositions and centroid decompositions. Our algorithm approximates the Wiener index within any desired multiplicative factor (1 ± ε) in time O(n ⋅ log n ⋅ k³ + √n ⋅ k/ε²), where n is the number of vertices of the graph and k is the treewidth. This time bound is almost-linear in n. Finally, we provide experimental results over standard benchmark molecules from PubChem and the Protein Data Bank, showcasing the applicability and scalability of our approach on real-world chemical graphs and comparing it with previous methods.
Cite as

Giovanna Kobus Conrado, Amir Kafshdar Goharshady, Pavel Hudec, Pingjiang Li, and Harshit Jitendra Motwani. Faster Treewidth-Based Approximations for Wiener Index. In 22nd International Symposium on Experimental Algorithms (SEA 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 301, pp. 6:1-6:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{conrado_et_al:LIPIcs.SEA.2024.6,
  author =	{Conrado, Giovanna Kobus and Goharshady, Amir Kafshdar and Hudec, Pavel and Li, Pingjiang and Motwani, Harshit Jitendra},
  title =	{{Faster Treewidth-Based Approximations for Wiener Index}},
  booktitle =	{22nd International Symposium on Experimental Algorithms (SEA 2024)},
  pages =	{6:1--6:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-325-6},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{301},
  editor =	{Liberti, Leo},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2024.6},
  URN =		{urn:nbn:de:0030-drops-203718},
  doi =		{10.4230/LIPIcs.SEA.2024.6},
  annote =	{Keywords: Computational Chemistry, Treewidth, Wiener Index}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2024.39
Optimal Bounds for Distinct Quartics

Authors: Panagiotis Charalampopoulos, Paweł Gawrychowski, and Samah Ghazawi

Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)

Abstract
A fundamental concept related to strings is that of repetitions. It has been extensively studied in many versions, from both purely combinatorial and algorithmic angles. One of the most basic questions is how many distinct squares, i.e., distinct strings of the form UU, a string of length n can contain as fragments. It turns out that this is always 𝒪(n), and the bound cannot be improved to sublinear in n [Fraenkel and Simpson, JCTA 1998]. Several similar questions about repetitions in strings have been considered, and by now we seem to have a good understanding of their repetitive structure. For higher-dimensional strings, the basic concept of periodicity has been successfully extended and applied to design efficient algorithms - it is inherently more complex than for regular strings. Extending the notion of repetitions and understanding the repetitive structure of higher-dimensional strings is however far from complete. Quartics were introduced by Apostolico and Brimkov [TCS 2000] as analogues of squares in two dimensions. Charalampopoulos, Radoszewski, Rytter, Waleń, and Zuba [ESA 2020] proved that the number of distinct quartics in an n×n 2D string is 𝒪(n²log²n) and that they can be computed in 𝒪(n²log²n) time. Gawrychowski, Ghazawi, and Landau [SPIRE 2021] constructed an infinite family of n×n 2D strings with Ω(n²log n) distinct quartics. This brings the challenge of determining asymptotically tight bounds. Here, we settle both the combinatorial and the algorithmic aspects of this question: the number of distinct quartics in an n×n 2D string is 𝒪(n²log n) and they can be computed in the worst-case optimal 𝒪(n²log n) time. As expected, our solution heavily exploits the periodic structure implied by occurrences of quartics. However, the two-dimensional nature of the problem introduces some technical challenges. Somewhat surprisingly, we overcome the final challenge for the combinatorial bound using a result of Marcus and Tardos [JCTA 2004] for permutation avoidance on matrices.
Cite as

Panagiotis Charalampopoulos, Paweł Gawrychowski, and Samah Ghazawi. Optimal Bounds for Distinct Quartics. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 39:1-39:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{charalampopoulos_et_al:LIPIcs.ICALP.2024.39,
  author =	{Charalampopoulos, Panagiotis and Gawrychowski, Pawe{\l} and Ghazawi, Samah},
  title =	{{Optimal Bounds for Distinct Quartics}},
  booktitle =	{51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)},
  pages =	{39:1--39:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-322-5},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{297},
  editor =	{Bringmann, Karl and Grohe, Martin and Puppis, Gabriele and Svensson, Ola},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2024.39},
  URN =		{urn:nbn:de:0030-drops-201823},
  doi =		{10.4230/LIPIcs.ICALP.2024.39},
  annote =	{Keywords: 2D strings, quartics, repetitions, periodicity}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2024.64
Minimizing Tardy Processing Time on a Single Machine in Near-Linear Time

Authors: Nick Fischer and Leo Wennmann

Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)

Abstract
In this work we revisit the elementary scheduling problem 1||∑ p_j U_j. The goal is to select, among n jobs with processing times and due dates, a subset of jobs with maximum total processing time that can be scheduled in sequence without violating their due dates. This problem is NP-hard, but a classical algorithm by Lawler and Moore from the 60s solves this problem in pseudo-polynomial time O(nP), where P is the total processing time of all jobs. With the aim to develop best-possible pseudo-polynomial-time algorithms, a recent wave of results has improved Lawler and Moore’s algorithm for 1||∑ p_j U_j: First to time Õ(P^{7/4}) [Bringmann, Fischer, Hermelin, Shabtay, Wellnitz; ICALP'20], then to time Õ(P^{5/3}) [Klein, Polak, Rohwedder; SODA'23], and finally to time Õ(P^{7/5}) [Schieber, Sitaraman; WADS'23]. It remained an exciting open question whether these works can be improved further. In this work we develop an algorithm in near-linear time Õ(P) for the 1||∑ p_j U_j problem. This running time not only significantly improves upon the previous results, but also matches conditional lower bounds based on the Strong Exponential Time Hypothesis or the Set Cover Hypothesis and is therefore likely optimal (up to subpolynomial factors). Our new algorithm also extends to the case of m machines in time Õ(P^m). In contrast to the previous improvements, we take a different, more direct approach inspired by the recent reductions from Modular Subset Sum to dynamic string problems. We thereby arrive at a satisfyingly simple algorithm.
Cite as

Nick Fischer and Leo Wennmann. Minimizing Tardy Processing Time on a Single Machine in Near-Linear Time. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 64:1-64:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{fischer_et_al:LIPIcs.ICALP.2024.64,
  author =	{Fischer, Nick and Wennmann, Leo},
  title =	{{Minimizing Tardy Processing Time on a Single Machine in Near-Linear Time}},
  booktitle =	{51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)},
  pages =	{64:1--64:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-322-5},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{297},
  editor =	{Bringmann, Karl and Grohe, Martin and Puppis, Gabriele and Svensson, Ola},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2024.64},
  URN =		{urn:nbn:de:0030-drops-202079},
  doi =		{10.4230/LIPIcs.ICALP.2024.64},
  annote =	{Keywords: Scheduling, Fine-Grained Complexity, Dynamic Strings}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2024.24
Dynamic Convex Hulls for Simple Paths

Authors: Bruce Brewer, Gerth Stølting Brodal, and Haitao Wang

Published in: LIPIcs, Volume 293, 40th International Symposium on Computational Geometry (SoCG 2024)

Abstract
We consider two restricted cases of the planar dynamic convex hull problem with point insertions and deletions. We assume all updates are performed on a deque (double-ended queue) of points. The first case considers the monotonic path case, where all points are sorted in a given direction, say horizontally left-to-right, and only the leftmost and rightmost points can be inserted and deleted. The second case, which is more general, assumes that the points in the deque constitute a simple path. For both cases, we present solutions supporting deque insertions and deletions in worst-case constant time and standard queries on the convex hull of the points in O(log n) time, where n is the number of points in the current point set. The convex hull of the current point set can be reported in O(h+log n) time, where h is the number of edges of the convex hull. For the 1-sided monotone path case, where updates are only allowed on one side, the reporting time can be reduced to O(h), and queries on the convex hull are supported in O(log h) time. All our time bounds are worst case. In addition, we prove lower bounds that match these time bounds, and thus our results are optimal.
Cite as

Bruce Brewer, Gerth Stølting Brodal, and Haitao Wang. Dynamic Convex Hulls for Simple Paths. In 40th International Symposium on Computational Geometry (SoCG 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 293, pp. 24:1-24:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{brewer_et_al:LIPIcs.SoCG.2024.24,
  author =	{Brewer, Bruce and Brodal, Gerth St{\o}lting and Wang, Haitao},
  title =	{{Dynamic Convex Hulls for Simple Paths}},
  booktitle =	{40th International Symposium on Computational Geometry (SoCG 2024)},
  pages =	{24:1--24:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-316-4},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{293},
  editor =	{Mulzer, Wolfgang and Phillips, Jeff M.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2024.24},
  URN =		{urn:nbn:de:0030-drops-199699},
  doi =		{10.4230/LIPIcs.SoCG.2024.24},
  annote =	{Keywords: Dynamic convex hull, convex hull queries, simple paths, path updates, deque}
}
Document
DOI: 10.4230/LIPIcs.SWAT.2024.17
Deterministic Cache-Oblivious Funnelselect

Authors: Gerth Stølting Brodal and Sebastian Wild

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

Abstract
In the multiple-selection problem one is given an unsorted array S of N elements and an array of q query ranks r_1 < ⋯ < r_q, and the task is to return, in sorted order, the q elements in S of rank r_1, …, r_q, respectively. The asymptotic deterministic comparison complexity of the problem was settled by Dobkin and Munro [JACM 1981]. In the I/O model an optimal I/O complexity was achieved by Hu et al. [SPAA 2014]. Recently [ESA 2023], we presented a cache-oblivious algorithm with matching I/O complexity, named funnelselect, since it heavily borrows ideas from the cache-oblivious sorting algorithm funnelsort from the seminal paper by Frigo, Leiserson, Prokop and Ramachandran [FOCS 1999]. Funnelselect is inherently randomized as it relies on sampling for cheaply finding many good pivots. In this paper we present deterministic funnelselect, achieving the same optimal I/O complexity cache-obliviously without randomization. Our new algorithm essentially replaces a single (in expectation) reversed-funnel computation using random pivots by a recursive algorithm using multiple reversed-funnel computations. To meet the I/O bound, this requires a carefully chosen subproblem size based on the entropy of the sequence of query ranks; deterministic funnelselect thus raises distinct technical challenges not met by randomized funnelselect. The resulting worst-case I/O bound is O(∑_{i = 1}^{q+1} Δ_i/B ⋅ log_{M/B} N/Δ_i + N/B), where B is the external memory block size, M ≥ B^{1+ε} is the internal memory size, for some constant ε > 0, and Δ_i = r_i - r_{i-1} (assuming r_0 = 0 and r_{q+1} = N + 1).
Cite as

Gerth Stølting Brodal and Sebastian Wild. Deterministic Cache-Oblivious Funnelselect. In 19th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 294, pp. 17:1-17:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{brodal_et_al:LIPIcs.SWAT.2024.17,
  author =	{Brodal, Gerth St{\o}lting and Wild, Sebastian},
  title =	{{Deterministic Cache-Oblivious Funnelselect}},
  booktitle =	{19th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2024)},
  pages =	{17:1--17:12},
  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.17},
  URN =		{urn:nbn:de:0030-drops-200576},
  doi =		{10.4230/LIPIcs.SWAT.2024.17},
  annote =	{Keywords: Multiple selection, cache-oblivious algorithm, entropy bounds}
}
Document
DOI: 10.4230/LIPIcs.FUN.2024.6
Bottom-Up Rebalancing Binary Search Trees by Flipping a Coin

Authors: Gerth Stølting Brodal

Published in: LIPIcs, Volume 291, 12th International Conference on Fun with Algorithms (FUN 2024)

Abstract
Rebalancing schemes for dynamic binary search trees are numerous in the literature, where the goal is to maintain trees of low height, either in the worst-case or expected sense. In this paper we study randomized rebalancing schemes for sequences of n insertions into an initially empty binary search tree, under the assumption that a tree only stores the elements and the tree structure without any additional balance information. Seidel (2009) presented a top-down randomized insertion algorithm, where insertions take expected O(lg² n) time, and the resulting trees have the same distribution as inserting a uniform random permutation into a binary search tree without rebalancing. Seidel states as an open problem if a similar result can be achieved with bottom-up insertions. In this paper we fail to answer this question. We consider two simple canonical randomized bottom-up insertion algorithms on binary search trees, assuming that an insertion is given the position where to insert the next element. The subsequent rebalancing is performed bottom-up in expected O(1) time, uses expected O(1) random bits, performs at most two rotations, and the rotations appear with geometrically decreasing probability in the distance from the leaf. For some insertion sequences the expected depth of each node is proved to be O(lg n). On the negative side, we prove for both algorithms that there exist simple insertion sequences where the expected depth is Ω(n), i.e., the studied rebalancing schemes are not competitive with (most) other rebalancing schemes in the literature.
Cite as

Gerth Stølting Brodal. Bottom-Up Rebalancing Binary Search Trees by Flipping a Coin. In 12th International Conference on Fun with Algorithms (FUN 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 291, pp. 6:1-6:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{brodal:LIPIcs.FUN.2024.6,
  author =	{Brodal, Gerth St{\o}lting},
  title =	{{Bottom-Up Rebalancing Binary Search Trees by Flipping a Coin}},
  booktitle =	{12th International Conference on Fun with Algorithms (FUN 2024)},
  pages =	{6:1--6:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-314-0},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{291},
  editor =	{Broder, Andrei Z. and Tamir, Tami},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2024.6},
  URN =		{urn:nbn:de:0030-drops-199143},
  doi =		{10.4230/LIPIcs.FUN.2024.6},
  annote =	{Keywords: Binary search tree, insertions, random rebalancing}
}
Document
DOI: 10.4230/DagRep.13.5.114
Scalable Data Structures (Dagstuhl Seminar 23211)

Authors: Gerth Stølting Brodal, John Iacono, László Kozma, Vijaya Ramachandran, and Justin Dallant

Published in: Dagstuhl Reports, Volume 13, Issue 5 (2023)

Abstract
This report documents the program and the outcomes of Dagstuhl Seminar 23211 "Scalable Data Structures". Data structures enable the organization, storage and retrieval of data across a variety of applications. As they are deployed at unprecedented scales, data structures can profoundly affect the efficiency of almost all computational tasks. The study of data structures thus continues to be an important and active area of research with an interplay between data structure design and analysis, developments in computer hardware, and the needs of modern applications. The extended abstracts included in this report give a snapshot of the current state of research on scalable data structures and establish directions for future developments in the field.
Cite as

Gerth Stølting Brodal, John Iacono, László Kozma, Vijaya Ramachandran, and Justin Dallant. Scalable Data Structures (Dagstuhl Seminar 23211). In Dagstuhl Reports, Volume 13, Issue 5, pp. 114-135, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@Article{brodal_et_al:DagRep.13.5.114,
  author =	{Brodal, Gerth St{\o}lting and Iacono, John and Kozma, L\'{a}szl\'{o} and Ramachandran, Vijaya and Dallant, Justin},
  title =	{{Scalable Data Structures (Dagstuhl Seminar 23211)}},
  pages =	{114--135},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2023},
  volume =	{13},
  number =	{5},
  editor =	{Brodal, Gerth St{\o}lting and Iacono, John and Kozma, L\'{a}szl\'{o} and Ramachandran, Vijaya and Dallant, Justin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagRep.13.5.114},
  URN =		{urn:nbn:de:0030-drops-193676},
  doi =		{10.4230/DagRep.13.5.114},
  annote =	{Keywords: algorithms, big data, computational models, data structures, GPU computing, parallel computation}
}
Document
DOI: 10.4230/LIPIcs.ESA.2023.25
Funnelselect: Cache-Oblivious Multiple Selection

Authors: Gerth Stølting Brodal and Sebastian Wild

Published in: LIPIcs, Volume 274, 31st Annual European Symposium on Algorithms (ESA 2023)

Abstract
We present the algorithm funnelselect, the first optimal randomized cache-oblivious algorithm for the multiple-selection problem. The algorithm takes as input an unsorted array of N elements and q query ranks r_1 < ⋯ < r_q, and returns in sorted order the q input elements of rank r_1, …, r_q, respectively. The algorithm uses expected and with high probability O(∑_{i = 1}^{q+1} Δ_i/B ⋅ log_{M/B} N/(Δ_i) + N/B) I/Os, where B is the external memory block size, M ≥ B^{1+ε} is the internal memory size, for some constant ε > 0, and Δ_i = r_i - r_{i-1} (assuming r_0 = 0 and r_{q+1} = N + 1). This is the best possible I/O bound in the cache-oblivious and external memory models. The result is achieved by reversing the computation of the cache-oblivious sorting algorithm funnelsort by Frigo, Leiserson, Prokop and Ramachandran [FOCS 1999], using randomly selected pivots for distributing elements, and pruning computations that with high probability are not expected to contain any query ranks.
Cite as

Gerth Stølting Brodal and Sebastian Wild. Funnelselect: Cache-Oblivious Multiple Selection. In 31st Annual European Symposium on Algorithms (ESA 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 274, pp. 25:1-25:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{brodal_et_al:LIPIcs.ESA.2023.25,
  author =	{Brodal, Gerth St{\o}lting and Wild, Sebastian},
  title =	{{Funnelselect: Cache-Oblivious Multiple Selection}},
  booktitle =	{31st Annual European Symposium on Algorithms (ESA 2023)},
  pages =	{25:1--25:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-295-2},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{274},
  editor =	{G{\o}rtz, Inge Li and Farach-Colton, Martin and Puglisi, Simon J. 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.2023.25},
  URN =		{urn:nbn:de:0030-drops-186789},
  doi =		{10.4230/LIPIcs.ESA.2023.25},
  annote =	{Keywords: Multiple selection, cache-oblivious algorithm, randomized algorithm, entropy bounds}
}
Document
Invited Talk
DOI: 10.4230/LIPIcs.STACS.2023.2
Amortised Analysis of Dynamic Data Structures (Invited Talk)

Authors: Eva Rotenberg

Published in: LIPIcs, Volume 254, 40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023)

Abstract
In dynamic data structures, one is interested in efficiently facilitating queries to a data set, while being able to efficiently perform updates as the data set undergoes changes. Often, relaxing the efficiency measure to the amortised setting allows for simpler algorithms. A well-known example of a data structure with amortised guarantees is the splay tree by Sleator and Tarjan [Daniel D. Sleator and Robert E. Tarjan, 1985]. Similarly, in data structures for dynamic graphs, one is interested in efficiently maintaining some information about the graph, or facilitating queries, as the graph undergoes changes in the form of insertion and deletion of edges. Examples of such information include connectivity, planarity, and approximate sparsity of the graph: is the graph presently connected? Is it planar? Has its arboricity grossly exceeded some specified number α̃? The related queries could be: is a connected to b? Are the edges uv and uw consecutive in the ordering around u in its current planar embedding? Or, report the O(α) out-edges of vertex x. In this talk, we will see Brodal and Fagerberg’s amortised algorithm for orienting sparse graphs (i.e. of arboricity ≤ α), so that each vertex has O(α) out-edges [Gerth Stølting Brodal and Rolf Fagerberg, 1999]. The algorithm itself is extremely simple, and uses an elegant amortised argument in its analysis. Then, we will visit the problem of dynamic planarity testing: is the graph presently planar? Here, we will see an elegant amortised reduction to the seemingly easier problem, where planarity-violating edges may be detected and rejected [Eppstein et al., 1996]. We will see a sketch of how the current state-of-the-art algorithm for efficient planarity testing [Jacob Holm and Eva Rotenberg, 2020] uses ideas similar to those in [Gerth Stølting Brodal and Rolf Fagerberg, 1999] to analyse the behaviour of a greedy algorithm via a possibly inefficient algorithm with provably low recourse [Jacob Holm and Eva Rotenberg, 2020]. If time permits, we will touch upon a recent simple amortised data structure for maintaining information in dynamic forests [Jacob Holm et al., 2023], which builds on ideas from splay trees. The talk concludes with some open questions in the area.
Cite as

Eva Rotenberg. Amortised Analysis of Dynamic Data Structures (Invited Talk). In 40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 254, pp. 2:1-2:2, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{rotenberg:LIPIcs.STACS.2023.2,
  author =	{Rotenberg, Eva},
  title =	{{Amortised Analysis of Dynamic Data Structures}},
  booktitle =	{40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023)},
  pages =	{2:1--2:2},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-266-2},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{254},
  editor =	{Berenbrink, Petra and Bouyer, Patricia and Dawar, Anuj and Kant\'{e}, Mamadou Moustapha},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2023.2},
  URN =		{urn:nbn:de:0030-drops-176547},
  doi =		{10.4230/LIPIcs.STACS.2023.2},
  annote =	{Keywords: Amortised analysis, splaying, dynamic graphs, planarity testing}
}
Document
DOI: 10.4230/LIPIcs.FUN.2022.8
Priority Queues with Decreasing Keys

Authors: Gerth Stølting Brodal

Published in: LIPIcs, Volume 226, 11th International Conference on Fun with Algorithms (FUN 2022)

Abstract
A priority queue stores a set of items with associated keys and supports the insertion of a new item and extraction of an item with minimum key. In applications like Dijkstra’s single source shortest path algorithm and Prim-Jarník’s minimum spanning tree algorithm, the key of an item can decrease over time. Usually this is handled by either using a priority queue supporting the deletion of an arbitrary item or a dedicated DecreaseKey operation, or by inserting the same item multiple times but with decreasing keys. In this paper we study what happens if the keys associated with items in a priority queue can decrease over time without informing the priority queue, and how such a priority queue can be used in Dijkstra’s algorithm. We show that binary heaps with bottom-up insertions fail to report items with unchanged keys in correct order, while binary heaps with top-down insertions report items with unchanged keys in correct order. Furthermore, we show that skew heaps, leftist heaps, and priority queues based on linking roots of heap-ordered trees, like pairing heaps, binomial queues and Fibonacci heaps, work correctly with decreasing keys without any modifications. Finally, we show that the post-order heap by Harvey and Zatloukal, a variant of a binary heap with amortized constant time insertions and amortized logarithmic time deletions, works correctly with decreasing keys and is a strong contender for an implicit priority queue supporting decreasing keys in practice.
Cite as

Gerth Stølting Brodal. Priority Queues with Decreasing Keys. In 11th International Conference on Fun with Algorithms (FUN 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 226, pp. 8:1-8:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{brodal:LIPIcs.FUN.2022.8,
  author =	{Brodal, Gerth St{\o}lting},
  title =	{{Priority Queues with Decreasing Keys}},
  booktitle =	{11th International Conference on Fun with Algorithms (FUN 2022)},
  pages =	{8:1--8:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-232-7},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{226},
  editor =	{Fraigniaud, Pierre and Uno, Yushi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2022.8},
  URN =		{urn:nbn:de:0030-drops-159787},
  doi =		{10.4230/LIPIcs.FUN.2022.8},
  annote =	{Keywords: priority queue, decreasing keys, post-order heap, Dijkstra’s algorithm}
}
Document
DOI: 10.4230/DagRep.11.1.1
Scalable Data Structures (Dagstuhl Seminar 21071)

Authors: Gerth Stølting Brodal, John Iacono, Markus E. Nebel, and Vijaya Ramachandran

Published in: Dagstuhl Reports, Volume 11, Issue 1 (2021)

Abstract
This report documents the program and the outcomes of Dagstuhl Seminar 21071 "Scalable Data Structure". Even if the field of data structures is quite mature, new trends and limitations in computer hardware together with the ever-increasing amounts of data that need to be processed raise new questions with respect to efficiency and continuously challenge the existing models of computation. Thermal and electrical power constraints have caused technology to reach "the power wall" with stagnating single processor performance, meaning that all nontrivial applications need to address scalability with multiple processors, a memory hierarchy and other communication challenges. Scalable data structures are pivotal to this process since they form the backbone of the algorithms driving these applications. The extended abstracts included in this report contain both recent state of the art advances and lay the foundation for new directions within data structures research.
Cite as

Gerth Stølting Brodal, John Iacono, Markus E. Nebel, and Vijaya Ramachandran. Scalable Data Structures (Dagstuhl Seminar 21071). In Dagstuhl Reports, Volume 11, Issue 1, pp. 1-23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@Article{brodal_et_al:DagRep.11.1.1,
  author =	{Brodal, Gerth St{\o}lting and Iacono, John and Nebel, Markus E. and Ramachandran, Vijaya},
  title =	{{Scalable Data Structures (Dagstuhl Seminar 21071)}},
  pages =	{1--23},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2021},
  volume =	{11},
  number =	{1},
  editor =	{Brodal, Gerth St{\o}lting and Iacono, John and Nebel, Markus E. and Ramachandran, Vijaya},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagRep.11.1.1},
  URN =		{urn:nbn:de:0030-drops-143481},
  doi =		{10.4230/DagRep.11.1.1},
  annote =	{Keywords: algorithms, big data, data structures, GPU computing, large data sets, models of computation, parallel algorithms}
}
Document
DOI: 10.4230/LIPIcs.SEA.2021.23
An Experimental Study of External Memory Algorithms for Connected Components

Authors: Gerth Stølting Brodal, Rolf Fagerberg, David Hammer, Ulrich Meyer, Manuel Penschuck, and Hung Tran

Published in: LIPIcs, Volume 190, 19th International Symposium on Experimental Algorithms (SEA 2021)

Abstract
We empirically investigate algorithms for solving Connected Components in the external memory model. In particular, we study whether the randomized O(Sort(E)) algorithm by Karger, Klein, and Tarjan can be implemented to compete with practically promising and simpler algorithms having only slightly worse theoretical cost, namely Borůvka’s algorithm and the algorithm by Sibeyn and collaborators. For all algorithms, we develop and test a number of tuning options. Our experiments are executed on a large set of different graph classes including random graphs, grids, geometric graphs, and hyperbolic graphs. Among our findings are: The Sibeyn algorithm is a very strong contender due to its simplicity and due to an added degree of freedom in its internal workings when used in the Connected Components setting. With the right tunings, the Karger-Klein-Tarjan algorithm can be implemented to be competitive in many cases. Higher graph density seems to benefit Karger-Klein-Tarjan relative to Sibeyn. Borůvka’s algorithm is not competitive with the two others.
Cite as

Gerth Stølting Brodal, Rolf Fagerberg, David Hammer, Ulrich Meyer, Manuel Penschuck, and Hung Tran. An Experimental Study of External Memory Algorithms for Connected Components. In 19th International Symposium on Experimental Algorithms (SEA 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 190, pp. 23:1-23:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{brodal_et_al:LIPIcs.SEA.2021.23,
  author =	{Brodal, Gerth St{\o}lting and Fagerberg, Rolf and Hammer, David and Meyer, Ulrich and Penschuck, Manuel and Tran, Hung},
  title =	{{An Experimental Study of External Memory Algorithms for Connected Components}},
  booktitle =	{19th International Symposium on Experimental Algorithms (SEA 2021)},
  pages =	{23:1--23:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-185-6},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{190},
  editor =	{Coudert, David and Natale, Emanuele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2021.23},
  URN =		{urn:nbn:de:0030-drops-137958},
  doi =		{10.4230/LIPIcs.SEA.2021.23},
  annote =	{Keywords: Connected Components, Experimental Evaluation, External Memory, Graph Algorithms, Randomization}
}
Document
DOI: 10.4230/DagRep.9.1.104
Data Structures for the Cloud and External Memory Data (Dagstuhl Seminar 19051)

Authors: Gerth Stølting Brodal, Ulrich Carsten Meyer, Bernhard E. Nebel, and Robert Sedgewick

Published in: Dagstuhl Reports, Volume 9, Issue 1 (2019)

Abstract
This report documents the program and the outcomes of Dagstuhl Seminar 16101 "Data Structures for the Cloud and External Memory Data". In today's computing environment vast amounts of data are processed, exchanged and analyzed. The manner in which information is stored profoundly influences the efficiency of these operations over the data. In spite of the maturity of the field many data structuring problems are still open, while new ones arise due to technological advances. The seminar covered both recent advances in the "classical" data structuring topics as well as new models of computation adapted to modern architectures, scientific studies that reveal the need for such models, applications where large data sets play a central role, modern computing platforms for very large data, and new data structures for large data in modern architectures. The extended abstracts included in this report contain both recent state of the art advances and lay the foundation for new directions within data structures research.
Cite as

Gerth Stølting Brodal, Ulrich Carsten Meyer, Bernhard E. Nebel, and Robert Sedgewick. Data Structures for the Cloud and External Memory Data (Dagstuhl Seminar 19051). In Dagstuhl Reports, Volume 9, Issue 1, pp. 104-124, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@Article{brodal_et_al:DagRep.9.1.104,
  author =	{Brodal, Gerth St{\o}lting and Meyer, Ulrich Carsten and Nebel, Bernhard E. and Sedgewick, Robert},
  title =	{{Data Structures for the Cloud and External Memory Data (Dagstuhl Seminar 19051)}},
  pages =	{104--124},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2019},
  volume =	{9},
  number =	{1},
  editor =	{Brodal, Gerth St{\o}lting and Meyer, Ulrich Carsten and Nebel, Bernhard E. and Sedgewick, Robert},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagRep.9.1.104},
  URN =		{urn:nbn:de:0030-drops-105722},
  doi =		{10.4230/DagRep.9.1.104},
  annote =	{Keywords: algorithms, big data, cloud computing, data structures, external memory methods, large data sets, web-scale}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2017.12
A Simple Greedy Algorithm for Dynamic Graph Orientation

Authors: Edvin Berglin and Gerth Stølting Brodal

Published in: LIPIcs, Volume 92, 28th International Symposium on Algorithms and Computation (ISAAC 2017)

Abstract
Graph orientations with low out-degree are one of several ways to efficiently store sparse graphs. If the graphs allow for insertion and deletion of edges, one may have to flip the orientation of some edges to prevent blowing up the maximum out-degree. We use arboricity as our sparsity measure. With an immensely simple greedy algorithm, we get parametrized trade-off bounds between out-degree and worst case number of flips, which previously only existed for amortized number of flips. We match the previous best worst-case algorithm (in O(log n) flips) for general arboricity and beat it for either constant or super-logarithmic arboricity. We also match a previous best amortized result for at least logarithmic arboricity, and give the first results with worst-case O(1) and O(sqrt(log n)) flips nearly matching degree bounds to their respective amortized solutions.
Cite as

Edvin Berglin and Gerth Stølting Brodal. A Simple Greedy Algorithm for Dynamic Graph Orientation. In 28th International Symposium on Algorithms and Computation (ISAAC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 92, pp. 12:1-12:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{berglin_et_al:LIPIcs.ISAAC.2017.12,
  author =	{Berglin, Edvin and St{\o}lting Brodal, Gerth},
  title =	{{A Simple Greedy Algorithm for Dynamic Graph Orientation}},
  booktitle =	{28th International Symposium on Algorithms and Computation (ISAAC 2017)},
  pages =	{12:1--12:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-054-5},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{92},
  editor =	{Okamoto, Yoshio and Tokuyama, Takeshi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2017.12},
  URN =		{urn:nbn:de:0030-drops-82637},
  doi =		{10.4230/LIPIcs.ISAAC.2017.12},
  annote =	{Keywords: Dynamic graph algorithms, graph arboricity, edge orientations}
}
Document
DOI: 10.4230/LIPIcs.ESA.2017.21
Cache Oblivious Algorithms for Computing the Triplet Distance Between Trees

Authors: Gerth Stølting Brodal and Konstantinos Mampentzidis

Published in: LIPIcs, Volume 87, 25th Annual European Symposium on Algorithms (ESA 2017)

Abstract
We study the problem of computing the triplet distance between two rooted unordered trees with n labeled leafs. Introduced by Dobson 1975, the triplet distance is the number of leaf triples that induce different topologies in the two trees. The current theoretically best algorithm is an O(nlogn) time algorithm by Brodal et al. [SODA 2013]. Recently Jansson et al. proposed a new algorithm that, while slower in theory, requiring O(n log^3 n) time, in practice it outperforms the theoretically faster O(n log n) algorithm. Both algorithms do not scale to external memory. We present two cache oblivious algorithms that combine the best of both worlds. The first algorithm is for the case when the two input trees are binary trees and the second a generalized algorithm for two input trees of arbitrary degree. Analyzed in the RAM model, both algorithms require O(n log n) time, and in the cache oblivious model O(n/B log_{2}(n/M)) I/Os. Their relative simplicity and the fact that they scale to external memory makes them achieve the best practical performance. We note that these are the first algorithms that scale to external memory, both in theory and practice, for this problem.
Cite as

Gerth Stølting Brodal and Konstantinos Mampentzidis. Cache Oblivious Algorithms for Computing the Triplet Distance Between Trees. In 25th Annual European Symposium on Algorithms (ESA 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 87, pp. 21:1-21:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{stltingbrodal_et_al:LIPIcs.ESA.2017.21,
  author =	{St{\o}lting Brodal, Gerth and Mampentzidis, Konstantinos},
  title =	{{Cache Oblivious Algorithms for Computing the Triplet Distance Between Trees}},
  booktitle =	{25th Annual European Symposium on Algorithms (ESA 2017)},
  pages =	{21:1--21:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-049-1},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{87},
  editor =	{Pruhs, Kirk and Sohler, Christian},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2017.21},
  URN =		{urn:nbn:de:0030-drops-78820},
  doi =		{10.4230/LIPIcs.ESA.2017.21},
  annote =	{Keywords: Phylogenetic tree, tree comparison, triplet distance, cache oblivious algorithm}
}
  • Refine by Author
  • 10 Brodal, Gerth Stølting
  • 3 Stølting Brodal, Gerth
  • 2 Iacono, John
  • 2 Ramachandran, Vijaya
  • 2 Wild, Sebastian
  • Show More...

  • Refine by Classification
  • 5 Theory of computation → Data structures design and analysis
  • 5 Theory of computation → Design and analysis of algorithms
  • 1 Mathematics of computing → Paths and connectivity problems
  • 1 Theory of computation → Computational geometry
  • 1 Theory of computation → Discrete optimization
  • Show More...

  • Refine by Keyword
  • 3 algorithms
  • 3 big data
  • 3 data structures
  • 2 GPU computing
  • 2 Multiple selection
  • Show More...

  • Refine by Type
  • 17 document

  • Refine by Publication Year
  • 6 2024
  • 3 2023
  • 2 2017
  • 2 2021
  • 1 2012
  • Show More...

© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact