11 Search Results for "Alstrup, Stephen"

Document
Invited Talk
DOI: 10.4230/LIPIcs.ESA.2024.2
Simple (Invited Talk)

Authors: Eva Rotenberg

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

Abstract
Simplicity in algorithms has various aspects; interpretations and implications. One is the simplicity of the algorithmic solution itself: if an algorithm (or data structure) has a brief verbal description or can be written with few lines of pseudocode, this can lead to easier, more robust, and possibly more efficient implementations. Another aspect of simplicity relates to the proofs of correctness and efficiency of our algorithmic solutions. Here, we experience that algorithms and data structures with simpler proofs of statements about their properties can be easier to understand, easier to teach, and sometimes, easier to generalise. Simplification of proofs also receives attention in mathematics; here, too, simplification has benefits to clarity of exposition and possibility of generalisation. There are even examples of proof simplification leading to the design of new and more efficient algorithms. This talk will present examples illustrating these various aspects of simplicity. Examples where algorithmic simplification or proof simplification has led to improved performance of algorithms and data structures, in theory, in practice, or both. Finally, some of the most attractive questions in discrete mathematics and in theory of computing have a property in common: they are very simple to pose, but surprisingly, to our knowledge, not very simple to answer. The talk will include examples of such questions, which I leave as an open problem for the audience.
Cite as

Eva Rotenberg. Simple (Invited Talk). In 32nd Annual European Symposium on Algorithms (ESA 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 308, pp. 2:1-2:2, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{rotenberg:LIPIcs.ESA.2024.2,
  author =	{Rotenberg, Eva},
  title =	{{Simple}},
  booktitle =	{32nd Annual European Symposium on Algorithms (ESA 2024)},
  pages =	{2:1--2:2},
  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.2},
  URN =		{urn:nbn:de:0030-drops-210739},
  doi =		{10.4230/LIPIcs.ESA.2024.2},
  annote =	{Keywords: Simplicity, graph algorithms, computational geometry, algorithmic simplification, data structures, combinatorics, proof simplification, dynamic graphs}
}
Document
DOI: 10.4230/LIPIcs.ESA.2024.30
Exact Minimum Weight Spanners via Column Generation

Authors: Fritz Bökler, Markus Chimani, Henning Jasper, and Mirko H. Wagner

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

Abstract
Given a weighted graph G, a minimum weight α-spanner is a least-weight subgraph H ⊆ G that preserves minimum distances between all node pairs up to a factor of α. There are many results on heuristics and approximation algorithms, including a recent investigation of their practical performance [Markus Chimani and Finn Stutzenstein, 2022]. Exact approaches, in contrast, have long been denounced as impractical: The first exact ILP (integer linear program) method [Sigurd and Zachariasen, 2004] from 2004 is based on a model with exponentially many path variables, solved via column generation. A second approach [Ahmed et al., 2019], modeling via arc-based multicommodity flow, was presented in 2019. In both cases, only graphs with 40-100 nodes were reported to be solvable. In this paper, we briefly report on a theoretical comparison between these two models from a polyhedral point of view, and then concentrate on improvements and engineering aspects. We evaluate their performance in a large-scale empirical study. We report that our tuned column generation approach, based on multicriteria shortest path computations, is able to solve instances with over 16 000 nodes within 13 min. Furthermore, now knowing optimal solutions for larger graphs, we are able to investigate the quality of the strongest known heuristic on reasonably sized instances for the first time.
Cite as

Fritz Bökler, Markus Chimani, Henning Jasper, and Mirko H. Wagner. Exact Minimum Weight Spanners via Column Generation. In 32nd Annual European Symposium on Algorithms (ESA 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 308, pp. 30:1-30:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{bokler_et_al:LIPIcs.ESA.2024.30,
  author =	{B\"{o}kler, Fritz and Chimani, Markus and Jasper, Henning and Wagner, Mirko H.},
  title =	{{Exact Minimum Weight Spanners via Column Generation}},
  booktitle =	{32nd Annual European Symposium on Algorithms (ESA 2024)},
  pages =	{30:1--30:17},
  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.30},
  URN =		{urn:nbn:de:0030-drops-211012},
  doi =		{10.4230/LIPIcs.ESA.2024.30},
  annote =	{Keywords: Graph spanners, ILP, algorithm engineering, experimental study}
}
Document
DOI: 10.4230/LIPIcs.ESA.2024.86
A Textbook Solution for Dynamic Strings

Authors: Zsuzsanna Lipták, Francesco Masillo, and Gonzalo Navarro

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

Abstract
We consider the problem of maintaining a collection of strings while efficiently supporting splits and concatenations on them, as well as comparing two substrings, and computing the longest common prefix between two suffixes. This problem can be solved in optimal time O(log N) whp for the updates and O(1) worst-case time for the queries, where N is the total collection size [Gawrychowski et al., SODA 2018]. We present here a much simpler solution based on a forest of enhanced splay trees (FeST), where both the updates and the substring comparison take O(log n) amortized time, n being the lengths of the strings involved. The longest common prefix of length 𝓁 is computed in O(log n + log²𝓁) amortized time. Our query results are correct whp. Our simpler solution enables other more general updates in O(log n) amortized time, such as reversing a substring and/or mapping its symbols. We can also regard substrings as circular or as their omega extension.
Cite as

Zsuzsanna Lipták, Francesco Masillo, and Gonzalo Navarro. A Textbook Solution for Dynamic Strings. In 32nd Annual European Symposium on Algorithms (ESA 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 308, pp. 86:1-86:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{liptak_et_al:LIPIcs.ESA.2024.86,
  author =	{Lipt\'{a}k, Zsuzsanna and Masillo, Francesco and Navarro, Gonzalo},
  title =	{{A Textbook Solution for Dynamic Strings}},
  booktitle =	{32nd Annual European Symposium on Algorithms (ESA 2024)},
  pages =	{86:1--86:16},
  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.86},
  URN =		{urn:nbn:de:0030-drops-211576},
  doi =		{10.4230/LIPIcs.ESA.2024.86},
  annote =	{Keywords: dynamic strings, splay trees, dynamic data structures, LCP, circular strings}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2024.63
Fully-Adaptive Dynamic Connectivity of Square Intersection Graphs

Authors: Ivor van der Hoog, André Nusser, Eva Rotenberg, and Frank Staals

Published in: LIPIcs, Volume 306, 49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024)

Abstract
A classical problem in computational geometry and graph algorithms is: given a dynamic set 𝒮 of geometric shapes in the plane, efficiently maintain the connectivity of the intersection graph of 𝒮. Previous papers studied the setting where, before the updates, the data structure receives some parameter P. Then, updates could insert and delete disks as long as at all times the disks have a diameter that lies in a fixed range [1/P, 1]. As a consequence of that prerequisite, the aspect ratio ψ (i.e. the ratio between the largest and smallest diameter) of the disks would at all times satisfy ψ ≤ P. The state-of-the-art for storing disks in a dynamic connectivity data structure is a data structure that uses O(Pn) space and that has amortized O(P log⁴ n) expected amortized update time. Connectivity queries between disks are supported in O(log n / log log n) time. In the dynamic setting, one wishes for a more flexible data structure in which disks of any diameter may arrive and leave, independent of their diameter, changing the aspect ratio freely. Ideally, the aspect ratio should merely be part of the analysis. We restrict our attention to axis-aligned squares, and study fully-dynamic square intersection graph connectivity. Our result is fully-adaptive to the aspect ratio, spending time proportional to the current aspect ratio ψ, as opposed to some previously given maximum P. Our focus on squares allows us to simplify and streamline the connectivity pipeline from previous work. When n is the number of squares and ψ is the aspect ratio after insertion (or before deletion), our data structure answers connectivity queries in O(log n / log log n) time. We can update connectivity information in O(ψ log⁴ n + log⁶ n) amortized time. We also improve space usage from O(P ⋅ n log n) to O(n log³ n log ψ) - while generalizing to a fully-adaptive aspect ratio - which yields a space usage that is near-linear in n for any polynomially bounded ψ.
Cite as

Ivor van der Hoog, André Nusser, Eva Rotenberg, and Frank Staals. Fully-Adaptive Dynamic Connectivity of Square Intersection Graphs. In 49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 306, pp. 63:1-63:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{vanderhoog_et_al:LIPIcs.MFCS.2024.63,
  author =	{van der Hoog, Ivor and Nusser, Andr\'{e} and Rotenberg, Eva and Staals, Frank},
  title =	{{Fully-Adaptive Dynamic Connectivity of Square Intersection Graphs}},
  booktitle =	{49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024)},
  pages =	{63:1--63:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-335-5},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{306},
  editor =	{Kr\'{a}lovi\v{c}, Rastislav and Ku\v{c}era, Anton{\'\i}n},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2024.63},
  URN =		{urn:nbn:de:0030-drops-206197},
  doi =		{10.4230/LIPIcs.MFCS.2024.63},
  annote =	{Keywords: Computational geometry, planar geometry, data structures, geometric intersection graphs, fully-dynamic algorithms}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2024.31
Tight Bounds on Adjacency Labels for Monotone Graph Classes

Authors: Édouard Bonnet, Julien Duron, John Sylvester, Viktor Zamaraev, and Maksim Zhukovskii

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

Abstract
A class of graphs admits an adjacency labeling scheme of size b(n), if the vertices in each of its n-vertex graphs can be assigned binary strings (called labels) of length b(n) so that the adjacency of two vertices can be determined solely from their labels. We give bounds on the size of adjacency labels for every family of monotone (i.e., subgraph-closed) classes with a "well-behaved" growth function between 2^Ω(n log n) and 2^O(n^{2-δ}) for any δ > 0. Specifically, we show that for any function f: ℕ → ℝ satisfying log n ⩽ f(n) ⩽ n^{1-δ} for any fixed δ > 0, and some sub-multiplicativity condition, there are monotone graph classes with growth 2^O(nf(n)) that do not admit adjacency labels of size at most f(n) log n. On the other hand, any such class does admit adjacency labels of size O(f(n)log n). Surprisingly this bound is a Θ(log n) factor away from the information-theoretic bound of Ω(f(n)). Our bounds are tight upto constant factors, and the special case when f = log implies that the recently-refuted Implicit Graph Conjecture [Hatami and Hatami, FOCS 2022] also fails within monotone classes. We further show that the Implicit Graph Conjecture holds for all monotone small classes. In other words, any monotone class with growth rate at most n! cⁿ for some constant c > 0, admits adjacency labels of information-theoretic order optimal size. In fact, we show a more general result that is of independent interest: any monotone small class of graphs has bounded degeneracy. We conjecture that the Implicit Graph Conjecture holds for all hereditary small classes.
Cite as

Édouard Bonnet, Julien Duron, John Sylvester, Viktor Zamaraev, and Maksim Zhukovskii. Tight Bounds on Adjacency Labels for Monotone Graph Classes. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 31:1-31:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{bonnet_et_al:LIPIcs.ICALP.2024.31,
  author =	{Bonnet, \'{E}douard and Duron, Julien and Sylvester, John and Zamaraev, Viktor and Zhukovskii, Maksim},
  title =	{{Tight Bounds on Adjacency Labels for Monotone Graph Classes}},
  booktitle =	{51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)},
  pages =	{31:1--31:20},
  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.31},
  URN =		{urn:nbn:de:0030-drops-201741},
  doi =		{10.4230/LIPIcs.ICALP.2024.31},
  annote =	{Keywords: Adjacency labeling, degeneracy, monotone classes, small classes, factorial classes, implicit graph conjecture}
}
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
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2023.74
Faster Submodular Maximization for Several Classes of Matroids

Authors: Monika Henzinger, Paul Liu, Jan Vondrák, and Da Wei Zheng

Published in: LIPIcs, Volume 261, 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)

Abstract
The maximization of submodular functions have found widespread application in areas such as machine learning, combinatorial optimization, and economics, where practitioners often wish to enforce various constraints; the matroid constraint has been investigated extensively due to its algorithmic properties and expressive power. Though tight approximation algorithms for general matroid constraints exist in theory, the running times of such algorithms typically scale quadratically, and are not practical for truly large scale settings. Recent progress has focused on fast algorithms for important classes of matroids given in explicit form. Currently, nearly-linear time algorithms only exist for graphic and partition matroids [Alina Ene and Huy L. Nguyen, 2019]. In this work, we develop algorithms for monotone submodular maximization constrained by graphic, transversal matroids, or laminar matroids in time near-linear in the size of their representation. Our algorithms achieve an optimal approximation of 1-1/e-ε and both generalize and accelerate the results of Ene and Nguyen [Alina Ene and Huy L. Nguyen, 2019]. In fact, the running time of our algorithm cannot be improved within the fast continuous greedy framework of Badanidiyuru and Vondrák [Ashwinkumar Badanidiyuru and Jan Vondrák, 2014]. To achieve near-linear running time, we make use of dynamic data structures that maintain bases with approximate maximum cardinality and weight under certain element updates. These data structures need to support a weight decrease operation and a novel Freeze operation that allows the algorithm to freeze elements (i.e. force to be contained) in its basis regardless of future data structure operations. For the laminar matroid, we present a new dynamic data structure using the top tree interface of Alstrup, Holm, de Lichtenberg, and Thorup [Stephen Alstrup et al., 2005] that maintains the maximum weight basis under insertions and deletions of elements in O(log n) time. This data structure needs to support certain subtree query and path update operations that are performed every insertion and deletion that are non-trivial to handle in conjunction. For the transversal matroid the Freeze operation corresponds to requiring the data structure to keep a certain set S of vertices matched, a property that we call S-stability. While there is a large body of work on dynamic matching algorithms, none are S-stable and maintain an approximate maximum weight matching under vertex updates. We give the first such algorithm for bipartite graphs with total running time linear (up to log factors) in the number of edges.
Cite as

Monika Henzinger, Paul Liu, Jan Vondrák, and Da Wei Zheng. Faster Submodular Maximization for Several Classes of Matroids. In 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 261, pp. 74:1-74:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{henzinger_et_al:LIPIcs.ICALP.2023.74,
  author =	{Henzinger, Monika and Liu, Paul and Vondr\'{a}k, Jan and Zheng, Da Wei},
  title =	{{Faster Submodular Maximization for Several Classes of Matroids}},
  booktitle =	{50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)},
  pages =	{74:1--74:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-278-5},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{261},
  editor =	{Etessami, Kousha and Feige, Uriel and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2023.74},
  URN =		{urn:nbn:de:0030-drops-181267},
  doi =		{10.4230/LIPIcs.ICALP.2023.74},
  annote =	{Keywords: submodular optimization, dynamic data structures, matching algorithms}
}
Document
DOI: 10.4230/LIPIcs.ESA.2019.4
Constructing Light Spanners Deterministically in Near-Linear Time

Authors: Stephen Alstrup, Søren Dahlgaard, Arnold Filtser, Morten Stöckel, and Christian Wulff-Nilsen

Published in: LIPIcs, Volume 144, 27th Annual European Symposium on Algorithms (ESA 2019)

Abstract
Graph spanners are well-studied and widely used both in theory and practice. In a recent breakthrough, Chechik and Wulff-Nilsen [Shiri Chechik and Christian Wulff-Nilsen, 2018] improved the state-of-the-art for light spanners by constructing a (2k-1)(1+epsilon)-spanner with O(n^(1+1/k)) edges and O_epsilon(n^(1/k)) lightness. Soon after, Filtser and Solomon [Arnold Filtser and Shay Solomon, 2016] showed that the classic greedy spanner construction achieves the same bounds. The major drawback of the greedy spanner is its running time of O(mn^(1+1/k)) (which is faster than [Shiri Chechik and Christian Wulff-Nilsen, 2018]). This makes the construction impractical even for graphs of moderate size. Much faster spanner constructions do exist but they only achieve lightness Omega_epsilon(kn^(1/k)), even when randomization is used. The contribution of this paper is deterministic spanner constructions that are fast, and achieve similar bounds as the state-of-the-art slower constructions. Our first result is an O_epsilon(n^(2+1/k+epsilon')) time spanner construction which achieves the state-of-the-art bounds. Our second result is an O_epsilon(m + n log n) time construction of a spanner with (2k-1)(1+epsilon) stretch, O(log k * n^(1+1/k) edges and O_epsilon(log k * n^(1/k)) lightness. This is an exponential improvement in the dependence on k compared to the previous result with such running time. Finally, for the important special case where k=log n, for every constant epsilon>0, we provide an O(m+n^(1+epsilon)) time construction that produces an O(log n)-spanner with O(n) edges and O(1) lightness which is asymptotically optimal. This is the first known sub-quadratic construction of such a spanner for any k = omega(1). To achieve our constructions, we show a novel deterministic incremental approximate distance oracle. Our new oracle is crucial in our construction, as known randomized dynamic oracles require the assumption of a non-adaptive adversary. This is a strong assumption, which has seen recent attention in prolific venues. Our new oracle allows the order of the edge insertions to not be fixed in advance, which is critical as our spanner algorithm chooses which edges to insert based on the answers to distance queries. We believe our new oracle is of independent interest.
Cite as

Stephen Alstrup, Søren Dahlgaard, Arnold Filtser, Morten Stöckel, and Christian Wulff-Nilsen. Constructing Light Spanners Deterministically in Near-Linear Time. In 27th Annual European Symposium on Algorithms (ESA 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 144, pp. 4:1-4:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{alstrup_et_al:LIPIcs.ESA.2019.4,
  author =	{Alstrup, Stephen and Dahlgaard, S{\o}ren and Filtser, Arnold and St\"{o}ckel, Morten and Wulff-Nilsen, Christian},
  title =	{{Constructing Light Spanners Deterministically in Near-Linear Time}},
  booktitle =	{27th Annual European Symposium on Algorithms (ESA 2019)},
  pages =	{4:1--4:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-124-5},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{144},
  editor =	{Bender, Michael A. and Svensson, Ola 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.2019.4},
  URN =		{urn:nbn:de:0030-drops-111255},
  doi =		{10.4230/LIPIcs.ESA.2019.4},
  annote =	{Keywords: Spanners, Light Spanners, Efficient Construction, Deterministic Dynamic Distance Oracle}
}
Document
DOI: 10.4230/LIPIcs.ICALP.2017.128
Near-Optimal Induced Universal Graphs for Bounded Degree Graphs

Authors: Mikkel Abrahamsen, Stephen Alstrup, Jacob Holm, Mathias Bæk Tejs Knudsen, and Morten Stöckel

Published in: LIPIcs, Volume 80, 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)

Abstract
A graph U is an induced universal graph for a family F of graphs if every graph in F is a vertex-induced subgraph of U. We give upper and lower bounds for the size of induced universal graphs for the family of graphs with n vertices of maximum degree D. Our new bounds improve several previous results except for the special cases where D is either near-constant or almost n/2. For constant even D Butler [Graphs and Combinatorics 2009] has shown O(n^(D/2)) and recently Alon and Nenadov [SODA 2017] showed the same bound for constant odd D. For constant D Butler also gave a matching lower bound. For generals graphs, which corresponds to D = n, Alon [Geometric and Functional Analysis, to appear] proved the existence of an induced universal graph with (1+o(1)) \cdot 2^((n-1)/2) vertices, leading to a smaller constant than in the previously best known bound of 16 * 2^(n/2) by Alstrup, Kaplan, Thorup, and Zwick [STOC 2015]. In this paper we give the following lower and upper bound of binom(floor(n/2))(floor(D/2)) * n^(-O(1)) and binom(floor(n/2))(floor(D/2)) * 2^(O(sqrt(D log D) * log(n/D))), respectively, where the upper bound is the main contribution. The proof that it is an induced universal graph relies on a randomized argument. We also give a deterministic upper bound of O(n^k / (k-1)!). These upper bounds are the best known when D <= n/2 - tilde-Omega(n^(3/4)) and either D is even and D = omega(1) or D is odd and D = omega(log n/log log n). In this range we improve asymptotically on the previous best known results by Butler [Graphs and Combinatorics 2009], Esperet, Arnaud and Ochem [IPL 2008], Adjiashvili and Rotbart [ICALP 2014], Alon and Nenadov [SODA 2017], and Alon [Geometric and Functional Analysis, to appear].
Cite as

Mikkel Abrahamsen, Stephen Alstrup, Jacob Holm, Mathias Bæk Tejs Knudsen, and Morten Stöckel. Near-Optimal Induced Universal Graphs for Bounded Degree Graphs. In 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 80, pp. 128:1-128:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{abrahamsen_et_al:LIPIcs.ICALP.2017.128,
  author =	{Abrahamsen, Mikkel and Alstrup, Stephen and Holm, Jacob and Knudsen, Mathias B{\ae}k Tejs and St\"{o}ckel, Morten},
  title =	{{Near-Optimal Induced Universal Graphs for Bounded Degree Graphs}},
  booktitle =	{44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)},
  pages =	{128:1--128:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-041-5},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{80},
  editor =	{Chatzigiannakis, Ioannis and Indyk, Piotr and Kuhn, Fabian and Muscholl, Anca},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2017.128},
  URN =		{urn:nbn:de:0030-drops-74114},
  doi =		{10.4230/LIPIcs.ICALP.2017.128},
  annote =	{Keywords: Adjacency labeling schemes, Bounded degree graphs, Induced universal graphs, Distributed computing}
}
Document
DOI: 10.4230/LIPIcs.ICALP.2016.132
Distance Labeling Schemes for Trees

Authors: Stephen Alstrup, Inge Li Gørtz, Esben Bistrup Halvorsen, and Ely Porat

Published in: LIPIcs, Volume 55, 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)

Abstract
We consider distance labeling schemes for trees: given a tree with n nodes, label the nodes with binary strings such that, given the labels of any two nodes, one can determine, by looking only at the labels, the distance in the tree between the two nodes. A lower bound by Gavoille et al. [Gavoille et al., J. Alg., 2004] and an upper bound by Peleg [Peleg, J. Graph Theory, 2000] establish that labels must use Theta(log^2(n)) bits. Gavoille et al. [Gavoille et al., ESA, 2001] show that for very small approximate stretch, labels use Theta(log(n) log(log(n))) bits. Several other papers investigate various variants such as, for example, small distances in trees [Alstrup et al., SODA, 2003]. We improve the known upper and lower bounds of exact distance labeling by showing that 1/4*log^2(n) bits are needed and that 1/2*log^2(n) bits are sufficient. We also give (1 + epsilon)-stretch labeling schemes using Theta(log(n)) bits for constant epsilon > 0. (1 + epsilon)-stretch labeling schemes with polylogarithmic label size have previously been established for doubling dimension graphs by Talwar [Talwar, STOC, 2004]. In addition, we present matching upper and lower bounds for distance labeling for caterpillars, showing that labels must have size 2*log(n) - Theta(log(log(n))). For simple paths with k nodes and edge weights in [1,n], we show that labels must have size (k - 1)/k*log(n) + Theta(log(k)).
Cite as

Stephen Alstrup, Inge Li Gørtz, Esben Bistrup Halvorsen, and Ely Porat. Distance Labeling Schemes for Trees. In 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 55, pp. 132:1-132:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{alstrup_et_al:LIPIcs.ICALP.2016.132,
  author =	{Alstrup, Stephen and G{\o}rtz, Inge Li and Halvorsen, Esben Bistrup and Porat, Ely},
  title =	{{Distance Labeling Schemes for Trees}},
  booktitle =	{43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)},
  pages =	{132:1--132:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-013-2},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{55},
  editor =	{Chatzigiannakis, Ioannis and Mitzenmacher, Michael and Rabani, Yuval and Sangiorgi, Davide},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2016.132},
  URN =		{urn:nbn:de:0030-drops-62661},
  doi =		{10.4230/LIPIcs.ICALP.2016.132},
  annote =	{Keywords: Distributed computing, Distance labeling, Graph theory, Routing, Trees}
}
Document
DOI: 10.4230/LIPIcs.ESA.2016.5
Sublinear Distance Labeling

Authors: Stephen Alstrup, Søren Dahlgaard, Mathias Bæk Tejs Knudsen, and Ely Porat

Published in: LIPIcs, Volume 57, 24th Annual European Symposium on Algorithms (ESA 2016)

Abstract
A distance labeling scheme labels the n nodes of a graph with binary strings such that, given the labels of any two nodes, one can determine the distance in the graph between the two nodes by looking only at the labels. A D-preserving distance labeling scheme only returns precise distances between pairs of nodes that are at distance at least D from each other. In this paper we consider distance labeling schemes for the classical case of unweighted and undirected graphs. We present a O(n/D * log^2(D)) bit D-preserving distance labeling scheme, improving the previous bound by Bollobás et al. [SIAM J. Discrete Math. 2005]. We also give an almost matching lower bound of Omega(n/D). With our D-preserving distance labeling scheme as a building block, we additionally achieve the following results: 1. We present the first distance labeling scheme of size o(n) for sparse graphs (and hence bounded degree graphs). This addresses an open problem by Gavoille et. al. [J. Algo. 2004], hereby separating the complexity from distance labeling in general graphs which require Omega(n) bits, Moon [Proc. of Glasgow Math. Association 1965]. 2. For approximate r-additive labeling schemes, that return distances within an additive error of r we show a scheme of size O(n/r * polylog(r*log(n))/log(n)) for r >= 2. This improves on the current best bound of O(n/r) by Alstrup et al. [SODA 2016] for sub-polynomial r, and is a generalization of a result by Gawrychowski et al. [arXiv preprint 2015] who showed this for r=2.
Cite as

Stephen Alstrup, Søren Dahlgaard, Mathias Bæk Tejs Knudsen, and Ely Porat. Sublinear Distance Labeling. In 24th Annual European Symposium on Algorithms (ESA 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 57, pp. 5:1-5:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{alstrup_et_al:LIPIcs.ESA.2016.5,
  author =	{Alstrup, Stephen and Dahlgaard, S{\o}ren and Knudsen, Mathias B{\ae}k Tejs and Porat, Ely},
  title =	{{Sublinear Distance Labeling}},
  booktitle =	{24th Annual European Symposium on Algorithms (ESA 2016)},
  pages =	{5:1--5:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-015-6},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{57},
  editor =	{Sankowski, Piotr and Zaroliagis, Christos},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2016.5},
  URN =		{urn:nbn:de:0030-drops-63479},
  doi =		{10.4230/LIPIcs.ESA.2016.5},
  annote =	{Keywords: Graph labeling schemes, Distance labeling, Graph theory, Sparse graphs}
}
  • Refine by Author
  • 4 Alstrup, Stephen
  • 2 Dahlgaard, Søren
  • 2 Knudsen, Mathias Bæk Tejs
  • 2 Porat, Ely
  • 2 Rotenberg, Eva
  • Show More...

  • Refine by Classification
  • 3 Theory of computation → Dynamic graph algorithms
  • 2 Theory of computation → Data structures design and analysis
  • 1 Mathematics of computing → Combinatorics
  • 1 Mathematics of computing → Graph theory
  • 1 Mathematics of computing → Submodular optimization and polymatroids
  • Show More...

  • Refine by Keyword
  • 2 Distance labeling
  • 2 Distributed computing
  • 2 Graph theory
  • 2 data structures
  • 2 dynamic data structures
  • Show More...

  • Refine by Type
  • 11 document

  • Refine by Publication Year
  • 6 2024
  • 2 2016
  • 1 2017
  • 1 2019
  • 1 2023

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