83 Search Results for "Italiano, Giuseppe F."

Volume

OASIcs, Volume 48

15th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2015)

ATMOS 2015, September 17, 2015, Patras, Greece

Editors: Giuseppe F. Italiano and Marie Schmidt

Document
DOI: 10.4230/LIPIcs.ITCS.2026.40
A Simple and Robust Protocol for Distributed Counting

Authors: Edith Cohen, Moshe Shechner, and Uri Stemmer

Published in: LIPIcs, Volume 362, 17th Innovations in Theoretical Computer Science Conference (ITCS 2026)

Abstract
We revisit the distributed counting problem, where a server must continuously approximate the total number of events occurring across k sites while minimizing communication. The communication complexity of this problem is known to be Θ(k/(ε)log N) for deterministic protocols. Huang, Yi, and Zhang (2012) showed that randomization can reduce this to Θ((√k)/ε log N), but their analysis is restricted to the oblivious setting, where the stream of events is independent of the protocol’s outputs. Xiong, Zhu, and Huang (2023) presented a robust protocol for distributed counting that removes the oblivious assumption. However, their communication complexity is suboptimal by a polylog(k) factor and their protocol is substantially more complex than the oblivious protocol of Huang et al. (2012). This left open a natural question: could it be that the simple protocol of Huang et al. (2012) is already robust? We resolve this question with two main contributions. First, we show that the protocol of Huang et al. (2012) is itself not robust by constructing an explicit adaptive attack that forces it to lose its accuracy. Second, we present a new, surprisingly simple, robust protocol for distributed counting that achieves the optimal communication complexity of O((√k)/ε log N). Our protocol is simpler than that of Xiong et al. (2023), perhaps even simpler than that of Huang et al. (2012), and is the first to match the optimal oblivious complexity in the adaptive setting.
Cite as

Edith Cohen, Moshe Shechner, and Uri Stemmer. A Simple and Robust Protocol for Distributed Counting. In 17th Innovations in Theoretical Computer Science Conference (ITCS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 362, pp. 40:1-40:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{cohen_et_al:LIPIcs.ITCS.2026.40,
  author =	{Cohen, Edith and Shechner, Moshe and Stemmer, Uri},
  title =	{{A Simple and Robust Protocol for Distributed Counting}},
  booktitle =	{17th Innovations in Theoretical Computer Science Conference (ITCS 2026)},
  pages =	{40:1--40:24},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-410-9},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{362},
  editor =	{Saraf, Shubhangi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2026.40},
  URN =		{urn:nbn:de:0030-drops-253272},
  doi =		{10.4230/LIPIcs.ITCS.2026.40},
  annote =	{Keywords: Distributed Streaming, Adversarial Streaming}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2026.102
Smoothed Analysis of Dynamic Graph Algorithms

Authors: Uri Meir and Ami Paz

Published in: LIPIcs, Volume 362, 17th Innovations in Theoretical Computer Science Conference (ITCS 2026)

Abstract
Recent years have seen significant progress in the study of dynamic graph algorithms, and most notably, the introduction of strong lower bound techniques for them (e.g., Henzinger, Krinninger, Nanongkai and Saranurak, STOC 2015; Larsen and Yu, FOCS 2023). As worst-case analysis (adversarial inputs) may lead to the necessity of high running times, a natural question arises: in which cases are high running times really necessary, and in which cases these inputs merely manifest unique pathological cases? Early attempts to tackle this question were made by Nikoletseas, Reif, Spirakis and Yung (ICALP 1995) and by Alberts and Henzinger (Algorithmica 1998), who considered models with very little adversarial control over the inputs, and showed fast algorithms exist for them. The question was then overlooked for decades, until Henzinger, Lincoln and Saha (SODA 2022) recently addressed uniformly random inputs, and presented algorithms and impossibility results for several subgraph counting problems. To tackle the above question more thoroughly, we employ smoothed analysis, a celebrated framework introduced by Spielman and Teng (J. ACM, 2004). An input is proposed by an adversary but then a noisy version of it is processed by the algorithm instead. This model of inputs is parameterized by the amount of adversarial control, and fully interpolates between worst-case inputs and a uniformly random input. Doing so, we extend impossibility results for some problems to the smoothed model with only a minor quantitative loss. That is, we show that partially-adversarial inputs suffice to impose high running times for certain problems. In contrast, we show that other problems become easy even with the slightest amount of noise. In addition, we study the interplay between the adversary and the noise, leading to three natural models of smoothed inputs, for which we show a hierarchy of increasing difficulty stretching between the average-case and the worst-case complexities.
Cite as

Uri Meir and Ami Paz. Smoothed Analysis of Dynamic Graph Algorithms. In 17th Innovations in Theoretical Computer Science Conference (ITCS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 362, pp. 102:1-102:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{meir_et_al:LIPIcs.ITCS.2026.102,
  author =	{Meir, Uri and Paz, Ami},
  title =	{{Smoothed Analysis of Dynamic Graph Algorithms}},
  booktitle =	{17th Innovations in Theoretical Computer Science Conference (ITCS 2026)},
  pages =	{102:1--102:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-410-9},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{362},
  editor =	{Saraf, Shubhangi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2026.102},
  URN =		{urn:nbn:de:0030-drops-253896},
  doi =		{10.4230/LIPIcs.ITCS.2026.102},
  annote =	{Keywords: Dynamic graph algorithms, Smoothed analysis, Shortest paths}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2026.5
Maximum-Flow and Minimum-Cut Sensitivity Oracles for Directed Graphs

Authors: Mridul Ahi, Keerti Choudhary, Shlok Pande, Pushpraj, and Lakshay Saggi

Published in: LIPIcs, Volume 362, 17th Innovations in Theoretical Computer Science Conference (ITCS 2026)

Abstract
This paper addresses the problem of designing fault-tolerant data structures for the (s,t)-max-flow and (s,t)-min-cut problems in unweighted directed graphs. Given a directed graph G = (V, E) with a designated source s, sink t, and an (s,t)-max-flow of value λ, we present constructions for max-flow and min-cut sensitivity oracles, and introduce the concept of a fault-tolerant flow family, which may be of independent interest. Our main contributions are as follows. 1) Fault-Tolerant Flow Family: We construct a family ℬ of 2λ+1 (s,t)-flows such that for every edge e, ℬ contains an (s,t)-max-flow of G-e. This covering property is tight up to constants for single failures and provably cannot extend to comparably small families for k ≥ 2, where we show an Ω(n) lower bound on the family size, independent of λ. 2) Max-Flow Sensitivity Oracle: Using the fault-tolerant flow family, we construct a single as well as dual-edge sensitivity oracle for (s,t)-max-flow that requires only O(λ n) space. Given any set F of up to two failing edges, the oracle reports the updated max-flow value in G-F in O(n) time. Additionally, for the single-failure case, the oracle can determine in constant time whether the flow through an edge x changes when another edge e fails. 3) Min-Cut Sensitivity Oracle for Dual Failures: Recently, Baswana et al. (ICALP’22) designed an O(n²)-sized oracle for answering (s,t)-min-cut size queries under dual edge failures in constant time, along with a matching lower bound. We extend this by focusing on graphs with small min-cut values λ, and present a more compact oracle of size O(λ n) that answers such min-cut size queries in constant time and reports the corresponding (s,t)-min-cut partition in O(n) time. We also show that the space complexity of our oracle is asymptotically optimal in this setting. 4) Min-Cut Sensitivity Oracle for Multiple Failures: We extend our results to the general case of k edge failures. For any graph with (s,t)-min-cut of size λ, we construct a k-fault-tolerant min-cut oracle with space complexity O_{λ,k}(n log n) that answers min-cut size queries in O_{λ,k}(log n) time. This also leads to improved fault-tolerant (s,t)-reachability oracles, achieving O(n log n) space and O(log n) query time for up to k = O(1) edge failures.
Cite as

Mridul Ahi, Keerti Choudhary, Shlok Pande, Pushpraj, and Lakshay Saggi. Maximum-Flow and Minimum-Cut Sensitivity Oracles for Directed Graphs. In 17th Innovations in Theoretical Computer Science Conference (ITCS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 362, pp. 5:1-5:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{ahi_et_al:LIPIcs.ITCS.2026.5,
  author =	{Ahi, Mridul and Choudhary, Keerti and Pande, Shlok and Pushpraj and Saggi, Lakshay},
  title =	{{Maximum-Flow and Minimum-Cut Sensitivity Oracles for Directed Graphs}},
  booktitle =	{17th Innovations in Theoretical Computer Science Conference (ITCS 2026)},
  pages =	{5:1--5:24},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-410-9},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{362},
  editor =	{Saraf, Shubhangi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2026.5},
  URN =		{urn:nbn:de:0030-drops-252920},
  doi =		{10.4230/LIPIcs.ITCS.2026.5},
  annote =	{Keywords: Fault tolerance, Data structures, Minimum cuts, Maximum flows}
}
Document
DOI: 10.4230/LIPIcs.IPEC.2025.16
Designing Compact ILPs via Fast Witness Verification

Authors: Michał Włodarczyk

Published in: LIPIcs, Volume 358, 20th International Symposium on Parameterized and Exact Computation (IPEC 2025)

Abstract
The standard formalization of preprocessing in parameterized complexity is given by kernelization. In this work, we depart from this paradigm and study a different type of preprocessing for problems without polynomial kernels, still aiming at producing instances that are easily solvable in practice. Specifically, we ask for which parameterized problems an instance (I,k) can be reduced in polynomial time to an integer linear program (ILP) with poly(k) constraints. We show that this property coincides with the parameterized complexity class WK[1], previously studied in the context of Turing kernelization lower bounds. In turn, the class WK[1] enjoys an elegant characterization in terms of witness verification protocols: a yes-instance should admit a witness of size poly(k) that can be verified in time poly(k). By combining known data structures with new ideas, we design such protocols for several problems, such as r-Way Cut, Vertex Multiway Cut, Steiner Tree, and Minimum Common String Partition, thus showing that they can be modeled by compact ILPs. We also present explicit ILP and MILP formulations for Weighted Vertex Cover on graphs with small (unweighted) vertex cover number. We believe that these results will provide a background for a systematic study of ILP-oriented preprocessing procedures for parameterized problems.
Cite as

Michał Włodarczyk. Designing Compact ILPs via Fast Witness Verification. In 20th International Symposium on Parameterized and Exact Computation (IPEC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 358, pp. 16:1-16:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{wlodarczyk:LIPIcs.IPEC.2025.16,
  author =	{W{\l}odarczyk, Micha{\l}},
  title =	{{Designing Compact ILPs via Fast Witness Verification}},
  booktitle =	{20th International Symposium on Parameterized and Exact Computation (IPEC 2025)},
  pages =	{16:1--16:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-407-9},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{358},
  editor =	{Agrawal, Akanksha and van Leeuwen, Erik Jan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2025.16},
  URN =		{urn:nbn:de:0030-drops-251481},
  doi =		{10.4230/LIPIcs.IPEC.2025.16},
  annote =	{Keywords: integer programming, kernelization, nondeterminism, multiway cut}
}
Document
DOI: 10.4230/LIPIcs.FSTTCS.2025.27
Fault-Tolerant Approximate Distance Oracles with a Source Set

Authors: Dipan Dey and Telikepalli Kavitha

Published in: LIPIcs, Volume 360, 45th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2025)

Abstract
Our input is an undirected weighted graph G = (V,E) on n vertices along with a source set S ⊆ V. The problem is to preprocess G and build a compact data structure such that upon query Qu(s,v,f) where (s,v) ∈ S×V and f is any faulty edge, we can quickly find a good estimate (i.e., within a small multiplicative stretch) of the s-v distance in G-f. We use a fault-tolerant ST-distance oracle from the work of Bilò et al. (STACS 2018) to construct an S×V approximate distance oracle or sourcewise approximate distance oracle of size Õ(|S|n + n^{3/2}) with multiplicative stretch at most 5. We construct another fault-tolerant sourcewise approximate distance oracle of size Õ(|S|n + n^{4/3}) with multiplicative stretch at most 13. Both the oracles have O(1) query answering time.
Cite as

Dipan Dey and Telikepalli Kavitha. Fault-Tolerant Approximate Distance Oracles with a Source Set. In 45th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 360, pp. 27:1-27:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{dey_et_al:LIPIcs.FSTTCS.2025.27,
  author =	{Dey, Dipan and Kavitha, Telikepalli},
  title =	{{Fault-Tolerant Approximate Distance Oracles with a Source Set}},
  booktitle =	{45th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2025)},
  pages =	{27:1--27:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-406-2},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{360},
  editor =	{Aiswarya, C. and Mehta, Ruta and Roy, Subhajit},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2025.27},
  URN =		{urn:nbn:de:0030-drops-251081},
  doi =		{10.4230/LIPIcs.FSTTCS.2025.27},
  annote =	{Keywords: Weighted graphs, approximate distances, fault-tolerant data structures}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2025.43
New Approximate Distance Oracles and Their Applications

Authors: Avi Kadria and Liam Roditty

Published in: LIPIcs, Volume 359, 36th International Symposium on Algorithms and Computation (ISAAC 2025)

Abstract
Let G = (V, E) be an undirected graph with n vertices and m edges, and let μ = m/n. A distance oracle is a data structure designed to answer approximate distance queries, with the goal of achieving low stretch, efficient space usage, and fast query time. While much of the prior work focused on distance oracles with constant query time, this paper presents a comprehensive study of distance oracles with non-constant query time. We explore the tradeoffs between space, stretch, and query time of distance oracles in various regimes. Specifically, we consider both weighted and unweighted graphs in the regimes of stretch < 2 and stretch ≥ 2. In addition, we demonstrate several applications of our new distance oracles to the n-Pairs Shortest Paths (n-PSP) problem and the All Nodes Shortest Cycles (ANSC) problem. Our main contributions are: - Weighted graphs: We present a new three-way trade-off between stretch, space, and query time, offering a natural extension of the classical Thorup–Zwick distance oracle [STOC’01 and JACM’05] to regimes with larger query time. Specifically, for any 0 < r < 1/2 and integer k ≥ 1, we construct a (2k(1 - 2r) - 1)-stretch distance oracle with Õ(m + n^{1 + 1/k}) space and Õ(μ n^r) query time. This construction provides an asymptotic improvement over the classical (2k - 1)-stretch and O(n^{1 + 1/k})-space tradeoff of Thorup and Zwick in sparse graphs, at the cost of increased query time. We also improve upon a result of Dalirrooyfard et al. [FOCS’22], who presented a (2k - 2)-stretch distance oracle with O(m + n^{1 + 1/k}) space and O(μ n^{1/k}) query time. In our oracle we reduce the stretch from (2k - 2) to (2k - 5) while preserving the same space and query time. - Unweighted graphs: We present a (2k - 5, 4 + 2_{odd})-approximation distance oracle with O(n^{1 + 1/k}) space and O(n^{1/k}) query time. This improves upon a (2k - 2, 2_{odd})-approximation distance oracle of Dalirrooyfard et al. [FOCS’22] while maintaining the same space and query time. We also present a distance oracle that given u,v ∈ V returns an estimate d̂(u,v) ≤ d(u,v) + 2⌈ d(u,v) / 3 ⌉ + 2, using O(n^{4/3 + 2ε}) space and O(n^{1 - 3ε}) query time. To the best of our knowledge, this is the first distance oracle that simultaneously achieves a multiplicative stretch < 2, and a space complexity O(n^{1.5 - α}), for some α > 0. - Applications for n-PSP and ANSC: We present an Õ(m^{1 - 1/(k+1)} n)-time algorithm for the n-PSP problem, that for every input pair ⟨s_i,t_i⟩, where i ∈ [n], returns an estimate d̂(s_i, t_i) such that d̂(s_i,t_i) ≤ d(s_i,t_i) + 2⌈d(s_i,t_i)/2k⌉. By allowing a small additive error, this result circumvents the conditional running time lower bound of Ω(m^{2 - 2/(k+1)} ⋅ n^{1/(k+1) - o(1)}), established by Dalirrooyfard et al. [FOCS’22] for achieving (1 + 1/k)-stretch. Additionally, we present an Õ(mn^{1 - 1/k})-time algorithm for the ANSC problem that computes, for every u ∈ V, an estimate ĉ_u such that ĉ_u ≤ SC(u) + 2⌈SC(u)/2(k - 1)⌉, where SC(u) denotes the length of the shortest cycle containing u. This improves upon the Õ(m^{2 - 2/k}n^{1/k})-time algorithm of Dalirrooyfard et al. [FOCS'22], while achieving the same approximation guarantee. We obtain our results by developing several new techniques, among them are the borderline vertices technique and the middle vertex technique, which may be of independent interest.
Cite as

Avi Kadria and Liam Roditty. New Approximate Distance Oracles and Their Applications. In 36th International Symposium on Algorithms and Computation (ISAAC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 359, pp. 43:1-43:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{kadria_et_al:LIPIcs.ISAAC.2025.43,
  author =	{Kadria, Avi and Roditty, Liam},
  title =	{{New Approximate Distance Oracles and Their Applications}},
  booktitle =	{36th International Symposium on Algorithms and Computation (ISAAC 2025)},
  pages =	{43:1--43:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-408-6},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{359},
  editor =	{Chen, Ho-Lin and Hon, Wing-Kai and Tsai, Meng-Tsung},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2025.43},
  URN =		{urn:nbn:de:0030-drops-249514},
  doi =		{10.4230/LIPIcs.ISAAC.2025.43},
  annote =	{Keywords: Distance oracles, Fine-grained algorithms, Graph algorithms, Data structures}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2025.24
Enumerating the Irreducible Closed Sets of an Acyclic Implicational Base of Bounded Degree

Authors: Oscar Defrain, Arthur Ohana, and Simon Vilmin

Published in: LIPIcs, Volume 359, 36th International Symposium on Algorithms and Computation (ISAAC 2025)

Abstract
We consider the problem of enumerating the irreducible closed sets of a closure system given by an implicational base. To date, the complexity status of this problem is widely open, and it is further known to generalize the notorious hypergraph dualization problem, even in the case of acyclic convex geometries, i.e., closure systems admitting an acyclic implicational base. This paper studies this case with a focus on the degree, which corresponds to the maximal number of implications in which an element occurs. We show that the problem is tractable for bounded values of this parameter, even when relaxed to the notions of premise- and conclusion-degree. Our algorithms rely on a sequential approach leveraging from acyclicity, combined with the solution graph traversal technique for the case of premise-degree. They are shown to perform in incremental-polynomial time. These results are complemented in the long version of this document by showing that the dual problem of constructing the implicational base can be solved in polynomial time. Finally, we argue that our running times cannot be improved to polynomial delay using the standard framework of flashlight search.
Cite as

Oscar Defrain, Arthur Ohana, and Simon Vilmin. Enumerating the Irreducible Closed Sets of an Acyclic Implicational Base of Bounded Degree. In 36th International Symposium on Algorithms and Computation (ISAAC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 359, pp. 24:1-24:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{defrain_et_al:LIPIcs.ISAAC.2025.24,
  author =	{Defrain, Oscar and Ohana, Arthur and Vilmin, Simon},
  title =	{{Enumerating the Irreducible Closed Sets of an Acyclic Implicational Base of Bounded Degree}},
  booktitle =	{36th International Symposium on Algorithms and Computation (ISAAC 2025)},
  pages =	{24:1--24:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-408-6},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{359},
  editor =	{Chen, Ho-Lin and Hon, Wing-Kai and Tsai, Meng-Tsung},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2025.24},
  URN =		{urn:nbn:de:0030-drops-249321},
  doi =		{10.4230/LIPIcs.ISAAC.2025.24},
  annote =	{Keywords: Algorithmic enumeration, closure systems, acyclic convex geometries, solution graph traversal, flashlight search, extension, hypergraph dualization}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2025.29
Space-Efficient Depth-First Search via Augmented Succinct Graph Encodings

Authors: Michael Elberfeld, Frank Kammer, and Johannes Meintrup

Published in: LIPIcs, Volume 359, 36th International Symposium on Algorithms and Computation (ISAAC 2025)

Abstract
We call a graph G separable if a balanced separator can be computed for G of size O(n^ε) with ε < 1. Many real-world graphs are separable such as graphs of bounded genus, graphs of constant treewidth, and graphs excluding a fixed minor. In particular, the well-known planar graphs are separable. We present a succinct encoding of separable graphs G such that, after the encoding is computed, any number of depth-first searches (DFS) can be performed from any given start vertex, each in o(n) time and o(n) bits in the word RAM model. After the execution of a DFS, the succinct encoding of G is augmented such that the DFS tree is encoded inside the encoding while maintaining succinctness. Afterward, the encoding provides common DFS-related queries in constant time. These queries include queries such as lowest-common ancestor of two given vertices in the DFS tree or queries that output the lowpoint of a given vertex in the DFS tree. Furthermore, for planar graphs, we show that the succinct encoding can be computed in O(n) bits and expected linear time, and a compact variant can be constructed in O(n) time and bits. For other separable graph classes 𝒢 the runtime and space usage depends on the specific algorithms used to find balanced separators in graphs of 𝒢.
Cite as

Michael Elberfeld, Frank Kammer, and Johannes Meintrup. Space-Efficient Depth-First Search via Augmented Succinct Graph Encodings. In 36th International Symposium on Algorithms and Computation (ISAAC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 359, pp. 29:1-29:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{elberfeld_et_al:LIPIcs.ISAAC.2025.29,
  author =	{Elberfeld, Michael and Kammer, Frank and Meintrup, Johannes},
  title =	{{Space-Efficient Depth-First Search via Augmented Succinct Graph Encodings}},
  booktitle =	{36th International Symposium on Algorithms and Computation (ISAAC 2025)},
  pages =	{29:1--29:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-408-6},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{359},
  editor =	{Chen, Ho-Lin and Hon, Wing-Kai and Tsai, Meng-Tsung},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2025.29},
  URN =		{urn:nbn:de:0030-drops-249379},
  doi =		{10.4230/LIPIcs.ISAAC.2025.29},
  annote =	{Keywords: Depth-First Search, Succinct, Space Efficient, Separable Graphs, Planar Graphs, Table Lookup, r-Division}
}
Document
DOI: 10.4230/LIPIcs.DISC.2025.30
Team Formation and Applications

Authors: Yuval Emek, Shay Kutten, Ido Rafael, and Gadi Taubenfeld

Published in: LIPIcs, Volume 356, 39th International Symposium on Distributed Computing (DISC 2025)

Abstract
A novel long-lived distributed problem, called Team Formation (TF), is introduced together with a message- and time-efficient randomized algorithm. The problem is defined over the asynchronous model with a complete communication graph, using bounded size messages, where a certain fraction of the nodes may experience a generalized, strictly stronger, version of initial failures. The goal of a TF algorithm is to assemble tokens injected by the environment, in a distributed manner, into teams of size σ, where σ is a parameter of the problem. The usefulness of TF is demonstrated by using it to derive efficient algorithms for many distributed problems. Specifically, we show that various (one-shot as well as long-lived) distributed problems reduce to TF. This includes well-known (and extensively studied) distributed problems such as several versions of leader election and threshold detection. For example, we are the first to break the linear message complexity bound for asynchronous implicit leader election. We also improve the time complexity of message-optimal algorithms for asynchronous explicit leader election. Other distributed problems that reduce to TF are new ones, including matching players in online gaming platforms, a generalization of gathering, constructing a perfect matching in an induced subgraph of the complete graph, and more. To complement our positive contribution, we establish a tight lower bound on the message complexity of TF algorithms.
Cite as

Yuval Emek, Shay Kutten, Ido Rafael, and Gadi Taubenfeld. Team Formation and Applications. In 39th International Symposium on Distributed Computing (DISC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 356, pp. 30:1-30:25, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{emek_et_al:LIPIcs.DISC.2025.30,
  author =	{Emek, Yuval and Kutten, Shay and Rafael, Ido and Taubenfeld, Gadi},
  title =	{{Team Formation and Applications}},
  booktitle =	{39th International Symposium on Distributed Computing (DISC 2025)},
  pages =	{30:1--30:25},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-402-4},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{356},
  editor =	{Kowalski, Dariusz R.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2025.30},
  URN =		{urn:nbn:de:0030-drops-248474},
  doi =		{10.4230/LIPIcs.DISC.2025.30},
  annote =	{Keywords: asynchronous message-passing, complete communication graph, initial failures, leader election, matching}
}
Document
DOI: 10.4230/LIPIcs.DISC.2025.38
Compact Routing Schemes in Undirected and Directed Graphs

Authors: Avi Kadria and Liam Roditty

Published in: LIPIcs, Volume 356, 39th International Symposium on Distributed Computing (DISC 2025)

Abstract
In this paper, we study the problem of compact routing schemes in weighted undirected and directed graphs. For weighted undirected graphs, more than a decade ago, Chechik [PODC'13] presented a ≈ 3.68k-stretch compact routing scheme that uses Õ(n^{1/k}log{D}) local storage, where D is the normalized diameter, for every k > 1. We present a ≈ 2.64k-stretch compact routing scheme that uses Õ(n^{1/k}) local storage on average in each vertex. This is the first compact routing scheme that uses total local storage of Õ(n^{1+1/k}) while achieving a c ⋅ k stretch, for a constant c < 3. In real-world network protocols, messages are usually transmitted as part of a communication session between two parties. Therefore, more than two decades ago, Thorup and Zwick [SPAA'01] considered compact routing schemes that establish a communication session using a handshake. In their handshake-based compact routing scheme, the handshake is routed along a (4k-5)-stretch path, and the rest of the communication session is routed along an optimal (2k-1)-stretch path. It is straightforward to improve the (4k-5)-stretch of the handshake to ≈ 3.68k-stretch using the compact routing scheme of Chechik [PODC'13]. We improve the handshake stretch to the optimal (2k-1), by borrowing the concept of roundtrip routing from directed graphs to undirected graphs. For weighted directed graphs, more than two decades ago, Roditty, Thorup, and Zwick [SODA'02 and TALG'08] presented a (4k+ε)-stretch compact roundtrip routing scheme that uses Õ(n^{1/k}) local storage for every k ≥ 3. For k = 3, this gives a (12+ε)-roundtrip stretch using Õ(n^{1/3}) local storage. We improve the stretch by developing a 7-roundtrip stretch routing scheme with Õ(n^{1/3}) local storage. In addition, we consider graphs with bounded hop diameter and present an optimal (2k-1)-roundtrip stretch routing scheme that uses Õ(D_{HOP}⋅ n^{1/k}), where D_{HOP} is the hop diameter of the graph.
Cite as

Avi Kadria and Liam Roditty. Compact Routing Schemes in Undirected and Directed Graphs. In 39th International Symposium on Distributed Computing (DISC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 356, pp. 38:1-38:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{kadria_et_al:LIPIcs.DISC.2025.38,
  author =	{Kadria, Avi and Roditty, Liam},
  title =	{{Compact Routing Schemes in Undirected and Directed Graphs}},
  booktitle =	{39th International Symposium on Distributed Computing (DISC 2025)},
  pages =	{38:1--38:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-402-4},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{356},
  editor =	{Kowalski, Dariusz R.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2025.38},
  URN =		{urn:nbn:de:0030-drops-248555},
  doi =		{10.4230/LIPIcs.DISC.2025.38},
  annote =	{Keywords: Routing schemes, Compact routing schemes, Distance oracles, Computer networks, Graph algorithms}
}
Document
Brief Announcement
DOI: 10.4230/LIPIcs.DISC.2025.63
Brief Announcement: Optimal Dispersion Under Asynchrony

Authors: Debasish Pattanayak, Ajay D. Kshemkalyani, Manish Kumar, Anisur Rahaman Molla, and Gokarna Sharma

Published in: LIPIcs, Volume 356, 39th International Symposium on Distributed Computing (DISC 2025)

Abstract
We study the dispersion problem in anonymous port-labeled graphs: k ≤ n mobile agents, each with a unique ID and initially located arbitrarily on the nodes of an n-node graph with maximum degree Δ, must autonomously relocate so that no node hosts more than one agent. Dispersion serves as a fundamental task in the distributed computing of mobile agents, and its complexity stems from key challenges in local coordination under anonymity and limited memory. The goal is to minimize both the time to achieve dispersion and the memory required per agent. It is known that any algorithm requires Ω(k) time in the worst case, and Ω(log k) bits of memory per agent. A recent result [Kshemkalyani et al., 2025] gives an optimal O(k)-time algorithm in the synchronous setting and an O(k log k)-time algorithm in the asynchronous setting, both using O(log(k+Δ)) bits. We close the complexity gap in the asynchronous setting by presenting the first dispersion algorithm that runs in optimal O(k) time using O(log(k+Δ)) bits of memory per agent. Our solution relies on a novel technique for constructing a port-one tree in anonymous graphs, which may be of independent interest.
Cite as

Debasish Pattanayak, Ajay D. Kshemkalyani, Manish Kumar, Anisur Rahaman Molla, and Gokarna Sharma. Brief Announcement: Optimal Dispersion Under Asynchrony. In 39th International Symposium on Distributed Computing (DISC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 356, pp. 63:1-63:7, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{pattanayak_et_al:LIPIcs.DISC.2025.63,
  author =	{Pattanayak, Debasish and Kshemkalyani, Ajay D. and Kumar, Manish and Molla, Anisur Rahaman and Sharma, Gokarna},
  title =	{{Brief Announcement: Optimal Dispersion Under Asynchrony}},
  booktitle =	{39th International Symposium on Distributed Computing (DISC 2025)},
  pages =	{63:1--63:7},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-402-4},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{356},
  editor =	{Kowalski, Dariusz R.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2025.63},
  URN =		{urn:nbn:de:0030-drops-248795},
  doi =		{10.4230/LIPIcs.DISC.2025.63},
  annote =	{Keywords: Distributed algorithms, mobile agents, local communication, dispersion, asynchrony, port-one tree, time and memory complexity}
}
Document
DOI: 10.4230/LIPIcs.ESA.2025.52
Beating Competitive Ratio 4 for Graphic Matroid Secretary

Authors: Kiarash Banihashem, MohammadTaghi Hajiaghayi, Dariusz R. Kowalski, Piotr Krysta, Danny Mittal, and Jan Olkowski

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

Abstract
One of the classic problems in online decision-making is the secretary problem, where the goal is to hire the best secretary out of n rankable applicants or, in a natural extension, to maximize the probability of selecting the largest number from a sequence arriving in random order. Many works have considered generalizations of this problem where one can accept multiple values subject to a combinatorial constraint. The seminal work of Babaioff, Immorlica, Kempe, and Kleinberg (SODA'07, JACM'18) proposed the matroid secretary conjecture, suggesting that there exists an O(1)-competitive algorithm for the matroid constraint, and many works since have attempted to obtain algorithms for both general matroids and specific classes of matroids. The ultimate goal of these results is to obtain an e-competitive algorithm, and the strong matroid secretary conjecture states that this is possible for general matroids. One of the most important classes of matroids is the graphic matroid, where a set of edges in a graph is deemed independent if it contains no cycle. Given the rich combinatorial structure of graphs, obtaining algorithms for these matroids is often seen as a good first step towards solving the problem for general matroids. For matroid secretary, Babaioff et al. (SODA'07, JACM'18) first studied graphic matroid case and obtained a 16-competitive algorithm. Subsequent works have improved the competitive ratio, most recently to 4 by Soto, Turkieltaub, and Verdugo (SODA'18). In this paper, we break the 4-competitive barrier for the problem, obtaining a new algorithm with a competitive ratio of 3.95. For the special case of simple graphs (i.e., graphs that do not contain parallel edges) we further improve this to 3.77. Intuitively, solving the problem for simple graphs is easier as they do not contain cycles of length two. A natural question that arises is whether we can obtain a ratio arbitrarily close to e by assuming the graph has a large enough girth. We answer this question affirmatively, proving that one can obtain a competitive ratio arbitrarily close to e even for constant values of girth, providing further evidence for the strong matroid secretary conjecture. We further show that this bound is tight: for any constant g, one cannot obtain a competitive ratio better than e even if we assume that the input graph has girth at least g. To our knowledge, such a bound was not previously known even for simple graphs.
Cite as

Kiarash Banihashem, MohammadTaghi Hajiaghayi, Dariusz R. Kowalski, Piotr Krysta, Danny Mittal, and Jan Olkowski. Beating Competitive Ratio 4 for Graphic Matroid Secretary. In 33rd Annual European Symposium on Algorithms (ESA 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 351, pp. 52:1-52:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{banihashem_et_al:LIPIcs.ESA.2025.52,
  author =	{Banihashem, Kiarash and Hajiaghayi, MohammadTaghi and Kowalski, Dariusz R. and Krysta, Piotr and Mittal, Danny and Olkowski, Jan},
  title =	{{Beating Competitive Ratio 4 for Graphic Matroid Secretary}},
  booktitle =	{33rd Annual European Symposium on Algorithms (ESA 2025)},
  pages =	{52:1--52:16},
  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.52},
  URN =		{urn:nbn:de:0030-drops-245205},
  doi =		{10.4230/LIPIcs.ESA.2025.52},
  annote =	{Keywords: online algorithms, graphic matroids, secretary problem}
}
Document
DOI: 10.4230/LIPIcs.ESA.2025.26
Faster Dynamic 2-Edge Connectivity in Directed Graphs

Authors: Loukas Georgiadis, Konstantinos Giannis, and Giuseppe F. Italiano

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

Abstract
Let G be a directed graph with n vertices and m edges. We present a deterministic algorithm that maintains the 2-edge-connected components of G under a sequence of m edge insertions, with a total running time of O(n² log n). This significantly improves upon the previous best bound of O(mn) for graphs that are not very sparse. After each insertion, our algorithm supports the following queries with asymptotically optimal efficiency: - Test in constant time whether two query vertices v and w are 2-edge-connected in G. - Report in O(n) time all the 2-edge-connected components of G. Our approach builds on the recent framework of Georgiadis, Italiano, and Kosinas [FOCS 2024] for computing the 3-edge-connected components of a directed graph in linear time, which leverages the minset-poset technique of Gabow [TALG 2016]. Additionally, we provide a deterministic decremental algorithm for maintaining 2-edge-connectivity in strongly connected directed graphs. Given a sequence of m edge deletions, our algorithm maintains the 2-edge-connected components in total time n^(2+o(1)), while supporting the same queries as the incremental algorithm. This result assumes that the edges of a fixed spanning tree of G and of its reverse graph G^R are not deleted. Previously, the best known bound for the decremental problem was O(mn log n), obtained by a randomized algorithm without restrictions on the deletions. In contrast to prior dynamic algorithms for 2-edge-connectivity in directed graphs, our method avoids the incremental computation of dominator trees, thereby circumventing the known conditional lower bound of Ω(mn).
Cite as

Loukas Georgiadis, Konstantinos Giannis, and Giuseppe F. Italiano. Faster Dynamic 2-Edge Connectivity in Directed Graphs. In 33rd Annual European Symposium on Algorithms (ESA 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 351, pp. 26:1-26:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{georgiadis_et_al:LIPIcs.ESA.2025.26,
  author =	{Georgiadis, Loukas and Giannis, Konstantinos and Italiano, Giuseppe F.},
  title =	{{Faster Dynamic 2-Edge Connectivity in Directed Graphs}},
  booktitle =	{33rd Annual European Symposium on Algorithms (ESA 2025)},
  pages =	{26:1--26:16},
  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.26},
  URN =		{urn:nbn:de:0030-drops-244945},
  doi =		{10.4230/LIPIcs.ESA.2025.26},
  annote =	{Keywords: Connectivity, dynamic algorithms, directed graphs}
}
Document
DOI: 10.4230/LIPIcs.ESA.2025.74
Core-Sparse Monge Matrix Multiplication: Improved Algorithm and Applications

Authors: Paweł Gawrychowski, Egor Gorbachev, and Tomasz Kociumaka

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

Abstract
Min-plus matrix multiplication is a fundamental tool for designing algorithms operating on distances in graphs and different problems solvable by dynamic programming. We know that, assuming the APSP hypothesis, no subcubic-time algorithm exists for the case of general matrices. However, in many applications the matrices admit certain structural properties that can be used to design faster algorithms. For example, when considering a planar graph, one often works with a Monge matrix A, meaning that the density matrix A^◻ has non-negative entries, that is, A^◻_{i,j} := A_{i+1,j} + A_{i,j+1} - A_{i,j} -A_{i+1,j+1} ≥ 0. The min-plus product of two n×n Monge matrices can be computed in 𝒪(n²) time using the famous SMAWK algorithm. In applications such as longest common subsequence, edit distance, and longest increasing subsequence, the matrices are even more structured, as observed by Tiskin [J. Discrete Algorithms, 2008]: they are (or can be converted to) simple unit-Monge matrices, meaning that the density matrix is a permutation matrix and, furthermore, the first column and the last row of the matrix consist of only zeroes. Such matrices admit an implicit representation of size 𝒪(n) and, as shown by Tiskin [SODA 2010 & Algorithmica, 2015], their min-plus product can be computed in 𝒪(nlog n) time. Russo [SPIRE 2010 & Theor. Comput. Sci., 2012] identified a general structural property of matrices that admit such efficient representation and min-plus multiplication algorithms: the core size δ, defined as the number of non-zero entries in the density matrices of the input and output matrices. He provided an adaptive implementation of the SMAWK algorithm that runs in 𝒪((n+δ)log³ n) or 𝒪((n+δ)log² n) time (depending on the representation of the input matrices). In this work, we further investigate the core size as the parameter that enables efficient min-plus matrix multiplication. On the combinatorial side, we provide a (linear) bound on the core size of the product matrix in terms of the core sizes of the input matrices. On the algorithmic side, we generalize Tiskin’s algorithm (but, arguably, with a more elementary analysis) to solve the core-sparse Monge matrix multiplication problem in 𝒪(n+δlog δ) ⊆ 𝒪(n + δ log n) time, matching the complexity for simple unit-Monge matrices. As witnessed by the recent work of Gorbachev and Kociumaka [STOC'25] for edit distance with integer weights, our generalization opens up the possibility of speed-ups for weighted sequence alignment problems. Furthermore, our multiplication algorithm is also capable of producing an efficient data structure for recovering the witness for any given entry of the output matrix. This allows us, for example, to preprocess an integer array of size n in Õ(n) time so that the longest increasing subsequence of any sub-array can be reconstructed in Õ(𝓁) time, where 𝓁 is the length of the reported subsequence. In comparison, Karthik C. S. and Rahul [arXiv, 2024] recently achieved 𝒪(𝓁+n^{1/2}polylog n)-time reporting after 𝒪(n^{3/2}polylog n)-time preprocessing.
Cite as

Paweł Gawrychowski, Egor Gorbachev, and Tomasz Kociumaka. Core-Sparse Monge Matrix Multiplication: Improved Algorithm and Applications. In 33rd Annual European Symposium on Algorithms (ESA 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 351, pp. 74:1-74:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{gawrychowski_et_al:LIPIcs.ESA.2025.74,
  author =	{Gawrychowski, Pawe{\l} and Gorbachev, Egor and Kociumaka, Tomasz},
  title =	{{Core-Sparse Monge Matrix Multiplication: Improved Algorithm and Applications}},
  booktitle =	{33rd Annual European Symposium on Algorithms (ESA 2025)},
  pages =	{74:1--74:17},
  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.74},
  URN =		{urn:nbn:de:0030-drops-245427},
  doi =		{10.4230/LIPIcs.ESA.2025.74},
  annote =	{Keywords: Min-plus matrix multiplication, Monge matrix, longest increasing subsequence}
}
  • Refine by Type
  • 82 Document/PDF
  • 42 Document/HTML
  • 1 Volume

  • Refine by Publication Year
  • 3 2026
  • 39 2025
  • 1 2024
  • 2 2023
  • 1 2022
  • Show More...

  • Refine by Author
  • 27 Italiano, Giuseppe F.
  • 11 Georgiadis, Loukas
  • 7 Parotsidis, Nikos
  • 5 Kosinas, Evangelos
  • 4 Karczmarz, Adam
  • Show More...

  • Refine by Series/Journal
  • 58 LIPIcs
  • 16 OASIcs
  • 1 TGDK
  • 3 DagRep
  • 4 DagSemProc

  • Refine by Classification
  • 11 Theory of computation → Dynamic graph algorithms
  • 9 Theory of computation → Graph algorithms analysis
  • 8 Mathematics of computing → Graph algorithms
  • 5 Theory of computation → Data structures design and analysis
  • 5 Theory of computation → Distributed algorithms
  • Show More...

  • Refine by Keyword
  • 4 Connectivity
  • 4 Graph Algorithms
  • 3 Data structures
  • 3 Graph algorithms
  • 2 Directed graphs
  • Show More...

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-2026 Schloss Dagstuhl – LZI GmbH Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact