DROPS

Document

DOI: 10.4230/LIPIcs.SWAT.2026.35

Path-Reporting Distance Oracles for Vertex-Labeled Graphs

Authors: Ofer Neiman and Alon Spector

Published in: LIPIcs, Volume 370, 20th Scandinavian Symposium on Algorithm Theory (SWAT 2026)

Abstract

Let G = (V,E) be a weighted undirected graph, with n vertices. A distance oracle is a data structure that can quickly answer distance queries, with some stretch factor. A seminal work of [Thorup and Zwick, 2005], given an integer k ≥ 1, provides such an oracle with stretch 2k-1, query time O(k), and size O(k⋅ n^{1+1/k}). Furthermore, this oracle can also report a path in G corresponding to the returned distance. In this paper we focus on vertex-labeled graphs, in which each vertex is given a label from a set L of size 𝓁. A vertex-label distance oracle answers queries of the form (v,λ), where v ∈ V and λ ∈ L, by reporting (an approximation to) the distance from v to the closest vertex of label λ. Following [Danny Hermelin et al., 2011], it was shown in [Chechik, 2012] that for any integer k > 1, there exists a vertex-label distance oracle with stretch 4k-5, query time O(k), and size O(k⋅ n⋅ 𝓁^{1/k}). This state-of-the-art result suffers from two main drawbacks: The stretch is roughly a factor of 2 larger than in [Thorup and Zwick, 2005], and it is not path-reporting. We address these concerns in this work, and provide the following results. - First, we devise a path-reporting vertex-label distance oracle, at the cost of a slight increase in stretch and size. For any constant 0 < ε < 1, our oracle has stretch (4k-5)⋅(1+ε), query time O(k), and size O(n^{1+o(1)}⋅ 𝓁^{1/k}). - Second, we show how to improve the stretch to the optimal 2k-1, at the cost of mildly increasing the query time. Specifically, we devise a vertex-label distance oracle with stretch 2k-1, query time O(𝓁^{1/k}⋅log n), and size O(k⋅ n⋅ 𝓁^{1/k}).

Cite as

Ofer Neiman and Alon Spector. Path-Reporting Distance Oracles for Vertex-Labeled Graphs. In 20th Scandinavian Symposium on Algorithm Theory (SWAT 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 370, pp. 35:1-35:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{neiman_et_al:LIPIcs.SWAT.2026.35,
  author =	{Neiman, Ofer and Spector, Alon},
  title =	{{Path-Reporting Distance Oracles for Vertex-Labeled Graphs}},
  booktitle =	{20th Scandinavian Symposium on Algorithm Theory (SWAT 2026)},
  pages =	{35:1--35:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-421-5},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{370},
  editor =	{Fraigniaud, Pierre},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2026.35},
  URN =		{urn:nbn:de:0030-drops-260719},
  doi =		{10.4230/LIPIcs.SWAT.2026.35},
  annote =	{Keywords: Graph Algorithms, Shortest Paths, Distance Oracles}
}

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.39

Going Beyond Surfaces in Diameter Approximation

Authors: Michał Włodarczyk

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

Abstract

Calculating the diameter of an undirected graph requires quadratic running time under the Strong Exponential Time Hypothesis and this barrier works even against any approximation better than 3/2. For planar graphs with positive edge weights, there are known (1+ε)-approximation algorithms with running time poly(1/ε, log n)⋅ n. However, these algorithms rely on shortest path separators and this technique falls short to yield efficient algorithms beyond graphs of bounded genus. In this work we depart from embedding-based arguments and obtain diameter approximations relying on VC set systems and the local treewidth property. We present two orthogonal extensions of the planar case by giving (1+ε)-approximation algorithms with the following running times: - 𝒪_h((1/ε)^𝒪(h) ⋅ nlog² n)-time algorithm for graphs excluding an apex graph of size h as a minor, - 𝒪_d((1/ε)^𝒪(d) ⋅ nlog² n)-time algorithm for the class of d-apex graphs. As a stepping stone, we obtain efficient (1+ε)-approximate distance oracles for graphs excluding an apex graph of size h as a minor. Our oracle has preprocessing time 𝒪_h((1/ε)⁸⋅ nlog nlog W) and query time 𝒪_h((1/ε)²⋅log n log W), where W is the metric stretch. Such oracles have been so far only known for bounded genus graphs. All our algorithms are deterministic.

Cite as

Michał Włodarczyk. Going Beyond Surfaces in Diameter Approximation. In 33rd Annual European Symposium on Algorithms (ESA 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 351, pp. 39:1-39:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{wlodarczyk:LIPIcs.ESA.2025.39,
  author =	{W{\l}odarczyk, Micha{\l}},
  title =	{{Going Beyond Surfaces in Diameter Approximation}},
  booktitle =	{33rd Annual European Symposium on Algorithms (ESA 2025)},
  pages =	{39:1--39:19},
  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.39},
  URN =		{urn:nbn:de:0030-drops-245076},
  doi =		{10.4230/LIPIcs.ESA.2025.39},
  annote =	{Keywords: diameter, approximation, distance oracles, graph minors, treewidth}
}

Document

DOI: 10.4230/LIPIcs.ESA.2025.36

Efficient Contractions of Dynamic Graphs - With Applications

Authors: Monika Henzinger, Evangelos Kosinas, Robin Münk, and Harald Räcke

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

Abstract

A non-trivial minimum cut (NMC) sparsifier is a multigraph Ĝ that preserves all non-trivial minimum cuts of a given undirected graph G. We introduce a flexible data structure for fully dynamic graphs that can efficiently provide an NMC sparsifier upon request at any point during the sequence of updates. We employ simple dynamic forest data structures to achieve a fast from-scratch construction of the sparsifier at query time. Based on the strength of the adversary and desired type of time bounds, the data structure comes with different guarantees. Specifically, let G be a fully dynamic simple graph with n vertices and minimum degree δ. Then our data structure supports an insertion/deletion of an edge to/from G in n^o(1) worst-case time. Furthermore, upon request, it can return w.h.p. an NMC sparsifier of G that has O(n/δ) vertices and O(n) edges, in Ô(n) time. The probabilistic guarantees hold against an adaptive adversary. Alternatively, the update and query times can be improved to Õ(1) and Õ(n) respectively, if amortized-time guarantees are sufficient, or if the adversary is oblivious. Throughout the paper, we use Õ to hide polylogarithmic factors and Ô to hide subpolynomial (i.e., n^o(1)) factors. We discuss two applications of our new data structure. First, it can be used to efficiently report a cactus representation of all minimum cuts of a fully dynamic simple graph. Building this cactus for the NMC sparsifier instead of the original graph allows for a construction time that is sublinear in the number of edges. Against an adaptive adversary, we can with high probability output the cactus representation in worst-case Ô(n) time. Second, our data structure allows us to efficiently compute the maximal k-edge-connected subgraphs of undirected simple graphs, by repeatedly applying a minimum cut algorithm on the NMC sparsifier. Specifically, we can compute with high probability the maximal k-edge-connected subgraphs of a simple graph with n vertices and m edges in Õ(m+n²/k) time. This improves the best known time bounds for k = Ω(n^{1/8}) and naturally extends to the case of fully dynamic graphs.

Cite as

Monika Henzinger, Evangelos Kosinas, Robin Münk, and Harald Räcke. Efficient Contractions of Dynamic Graphs - With Applications. In 33rd Annual European Symposium on Algorithms (ESA 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 351, pp. 36:1-36:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{henzinger_et_al:LIPIcs.ESA.2025.36,
  author =	{Henzinger, Monika and Kosinas, Evangelos and M\"{u}nk, Robin and R\"{a}cke, Harald},
  title =	{{Efficient Contractions of Dynamic Graphs - With Applications}},
  booktitle =	{33rd Annual European Symposium on Algorithms (ESA 2025)},
  pages =	{36:1--36:14},
  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.36},
  URN =		{urn:nbn:de:0030-drops-245047},
  doi =		{10.4230/LIPIcs.ESA.2025.36},
  annote =	{Keywords: Graph Algorithms, Cut Sparsifiers, Dynamic Algorithms}
}

Document

Invited Talk

DOI: 10.4230/LIPIcs.MFCS.2025.2

Higher Connectivity in Directed Graphs (Invited Talk)

Authors: Giuseppe F. Italiano

Published in: LIPIcs, Volume 345, 50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025)

Abstract

The computation of edge-connected components in directed and undirected graphs is a well studied problem that is motivated by several applications (see, e.g., [Hiroshi Nagamochi and Toshihide Ibaraki, 2008]). Let G = (V,E) be a strongly connected directed graph with m edges and n vertices. An edge e ∈ E is a strong bridge if G ⧵ e is not strongly connected. More generally, a set of edges C ⊆ E is a cut if G ⧵ C is not strongly connected. If |C| = k then we refer to C as a k-sized cut of G. Hence, a strong bridge is a 1-sized cut of G. A digraph G is k-edge-connected if it has no (k-1)-cuts. We say that two vertices v and w are k-edge-connected, and we denote this relation by v ↔_{k} w, if there are k edge-disjoint directed paths from v to w and k edge-disjoint directed paths from w to v. (Note that a path from v to w and a path from w to v need not be edge-disjoint). By Menger’s theorem [Karl Menger, 1927], v ↔_{k} w if and only if the removal of any set of at most k-1 edges leaves v and w in the same strongly connected component. We define a k-edge-connected component of a digraph G = (V,E) as a maximal subset U ⊆ V such that u ↔_{k} v for all u, v ∈ U. The k-edge-connected components of G form a partition of V, since v ↔_{k} w is an equivalence relation [Loukas Georgiadis et al., 2016]. Connectivity-related problems are known to be much more difficult in directed graphs than in undirected graphs (see, e.g., [Harold N. Gabow, 2016; Monika Henzinger et al., 2020; Ken-Ichi Kawarabayashi and Mikkel Thorup, 2018]). Indeed, there is a fundamental difference in the structure of the cuts in the two scenarios. Specifically, it has been established more than 60 years ago [Gomory and Hu, 1961] that edge cuts in undirected graphs have a nice structure, as defined by the Gomory-Hu tree (or cut tree), which plays a special role in identifying, for any k, the k-edge-connected components of undirected graphs. Furthermore, many efficient algorithms for computing Gomory-Hu trees are available (see e.g., [Amir Abboud et al., 2021; Amir Abboud et al., 2022; Amir Abboud et al., 2023; Chen et al., 2022; Hariharan et al., 2007; Li et al., 2022]). On the contrary, in directed graphs edge cuts have a more complicated structure, and it was proved by Benczúr [Benczúr, 1995] that in this case cut trees do not even exist. It is thus not surprising that, while it is known how to compute the k-edge-connected components of undirected graphs in linear time for k ≤ 5 [Harold N. Gabow, 2000; Zvi Galil and Giuseppe F. Italiano, 1991; Loukas Georgiadis et al., 2021; John E. Hopcroft and Robert E. Tarjan, 1973; Kosinas, 2024; Wojciech Nadara et al., 2021; Hiroshi Nagamochi and Toshihide Ibaraki, 1992; Robert E. Tarjan, 1972; Yung H. Tsin, 2009], the situation is more challenging for directed graphs, where linear-time algorithms are only known for k ≤ 2 [Robert E. Tarjan, 1972; Loukas Georgiadis et al., 2020]. Also, as argued in [Loukas Georgiadis et al., 2023], there is a substantial increase in the inherent difficulty of the problem of computing k-edge-connected components in digraphs for k = 3 compared to k = 2. Indeed, for k = 2 any pair of vertices s,t that are not 2-edge-connected can be separated by only O(n) s-t min-cuts of size 1, for which we can define a total order [Giuseppe F. Italiano et al., 2012]. For k = 3, any pair of vertices s,t that are 2-edge-connected but not 3-edge-connected, can be separated by as many as O(n²) s-t min-cuts of size 2, which are also not totally ordered. This makes it difficult to explore the effect of removing each such cut of size 2 on the strong connectivity of the graph, similar to what was done for the case of k = 2 [Loukas Georgiadis et al., 2020]. Until recently, the best-known bound for computing the k-edge-connected components of a digraph, for constant k ≥ 3, was O(mn) by Nagamochi and Watanabe [Hiroshi Nagamochi and Toshimasa Watanabe, 1993]. Georgiadis et al. [Loukas Georgiadis et al., 2023] presented a randomized (Monte-Carlo) algorithm that computes the 3-edge-connected components of a digraph with m edges in Õ(m^{3/2}) time. Their algorithm involves a nontrivial extension of the framework of [Forster et al., 2020; Nanongkai et al., 2019] for deciding whether a digraph is (k+1)-edge-connected. It applies a local search procedure [Shiri Chechik et al., 2017; Forster et al., 2020] for identifying 2-in or 2-out sets, i.e., vertex sets S ⊆ V such that there are at most 2 edges from V ⧵ S to S or from S to V⧵ S. After finding such a set S, [Loukas Georgiadis et al., 2023] applies an efficient graph operation for replacing S with a gadget of small size that preserves the pairwise connectivity among the vertices of V ⧵ S. As in [Forster et al., 2020; Nanongkai et al., 2019], local search is initiated from sampled edges, but the overall scheme is more complicated to guarantee that enough 2-in sets or 2-out sets are identified that separate vertices that are not 3-edge-connected. Recently, Georgiadis, Italiano and Kosinas [Georgiadis et al., 2024] improved significantly the bound of [Loukas Georgiadis et al., 2023] by showing how to compute the 3-edge-connected components of a digraph in linear time with a deterministic algorithm. Their algorithm differs substantially from [Loukas Georgiadis et al., 2023], as it is based on a new characterization of 2-sized cuts in digraphs, which requires new techniques and a suitable combination of the notions of 2-connectivity-light graphs [Loukas Georgiadis et al., 2023] and of maximally edge-disjoint strongly divergent spanning trees [Loukas Georgiadis and Robert E. Tarjan, 2015; Robert E. Tarjan, 1976]. In particular, Georgiadis, Italiano and Kosinas [Georgiadis et al., 2024] showed how to modify the minset-poset technique of Gabow [Harold N. Gabow, 2016], in order to find the 3-edge-connected components of a digraph with m edges in O(m) time. In the invited talk, I will survey some of this recent work on higher connectivity on directed graphs.

Cite as

Giuseppe F. Italiano. Higher Connectivity in Directed Graphs (Invited Talk). In 50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 345, pp. 2:1-2:4, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{italiano:LIPIcs.MFCS.2025.2,
  author =	{Italiano, Giuseppe F.},
  title =	{{Higher Connectivity in Directed Graphs}},
  booktitle =	{50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025)},
  pages =	{2:1--2:4},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-388-1},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{345},
  editor =	{Gawrychowski, Pawe{\l} and Mazowiecki, Filip and Skrzypczak, Micha{\l}},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2025.2},
  URN =		{urn:nbn:de:0030-drops-241096},
  doi =		{10.4230/LIPIcs.MFCS.2025.2},
  annote =	{Keywords: Connectivity, Directed graphs, Graph algorithms}
}

Document

Invited Talk

DOI: 10.4230/LIPIcs.CONCUR.2025.3

On-The-Fly Verification: Advancements in Dependency Graphs (Invited Talk)

Authors: Jiří Srba

Published in: LIPIcs, Volume 348, 36th International Conference on Concurrency Theory (CONCUR 2025)

Abstract

Dependency graphs have emerged as a versatile and powerful formalism with wide-ranging applications in formal verification. In this extended abstract, we provide an overview of selected advancements in on-the-fly verification techniques based on dependency graphs, focusing on the recent developments, optimizations and generalizations of this generic verification framework.

Cite as

Jiří Srba. On-The-Fly Verification: Advancements in Dependency Graphs (Invited Talk). In 36th International Conference on Concurrency Theory (CONCUR 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 348, pp. 3:1-3:5, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{srba:LIPIcs.CONCUR.2025.3,
  author =	{Srba, Ji\v{r}{\'\i}},
  title =	{{On-The-Fly Verification: Advancements in Dependency Graphs}},
  booktitle =	{36th International Conference on Concurrency Theory (CONCUR 2025)},
  pages =	{3:1--3:5},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-389-8},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{348},
  editor =	{Bouyer, Patricia and van de Pol, Jaco},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CONCUR.2025.3},
  URN =		{urn:nbn:de:0030-drops-239534},
  doi =		{10.4230/LIPIcs.CONCUR.2025.3},
  annote =	{Keywords: dependency graphs, Boolean equation systems, on-the-fly algorithms, fixed-point computation, applications}
}

Document

Track A: Algorithms, Complexity and Games

DOI: 10.4230/LIPIcs.ICALP.2025.33

Faster Construction of a Planar Distance Oracle with Õ(1) Query Time

Authors: Itai Boneh, Shay Golan, Shay Mozes, Daniel Prigan, and Oren Weimann

Published in: LIPIcs, Volume 334, 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)

Abstract

We show how to preprocess a weighted undirected n-vertex planar graph in Õ(n^{4/3}) time, such that the distance between any pair of vertices can then be reported in Õ(1) time. This improves the previous Õ(n^{3/2}) preprocessing time [JACM'23]. Our main technical contribution is a near optimal construction of additively weighted Voronoi diagrams in undirected planar graphs. Namely, given a planar graph G and a face f, we show that one can preprocess G in Õ(n) time such that given any weight assignment to the vertices of f one can construct the additively weighted Voronoi diagram of f in near optimal Õ(|f|) time. This improves the Õ(√{n|f|}) construction time of [JACM'23].

Cite as

Itai Boneh, Shay Golan, Shay Mozes, Daniel Prigan, and Oren Weimann. Faster Construction of a Planar Distance Oracle with Õ(1) Query Time. In 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 334, pp. 33:1-33:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{boneh_et_al:LIPIcs.ICALP.2025.33,
  author =	{Boneh, Itai and Golan, Shay and Mozes, Shay and Prigan, Daniel and Weimann, Oren},
  title =	{{Faster Construction of a Planar Distance Oracle with \~{O}(1) Query Time}},
  booktitle =	{52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)},
  pages =	{33:1--33:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-372-0},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{334},
  editor =	{Censor-Hillel, Keren and Grandoni, Fabrizio and Ouaknine, Jo\"{e}l 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.2025.33},
  URN =		{urn:nbn:de:0030-drops-234106},
  doi =		{10.4230/LIPIcs.ICALP.2025.33},
  annote =	{Keywords: Distance Oracle, Planar Graph, Construction Time}
}

Document

Resource Paper

DOI: 10.4230/TGDK.2.2.5

The Reasonable Ontology Templates Framework

Authors: Martin Georg Skjæveland and Leif Harald Karlsen

Published in: TGDK, Volume 2, Issue 2 (2024): Special Issue on Resources for Graph Data and Knowledge. Transactions on Graph Data and Knowledge, Volume 2, Issue 2

Abstract

Reasonable Ontology Templates (OTTR) is a templating language for representing and instantiating patterns. It is based on simple and generic, but powerful, mechanisms such as recursive macro expansion, term substitution and type systems, and is designed particularly for building and maintaining RDF knowledge graphs and OWL ontologies. In this resource paper, we present the formal specifications that define the OTTR framework. This includes the fundamentals of the OTTR language and the adaptions to make it fit with standard semantic web languages, and two serialization formats developed for semantic web practitioners. We also present the OTTR framework’s support for documenting, publishing and managing template libraries, and for tools for practical bulk instantiation of templates from tabular data and queryable data sources. The functionality of the OTTR framework is available for use through Lutra, an open-source reference implementation, and other independent implementations. We report on the use and impact of OTTR by presenting selected industrial use cases. Finally, we reflect on some design considerations of the language and framework and present ideas for future work.

Cite as

Martin Georg Skjæveland and Leif Harald Karlsen. The Reasonable Ontology Templates Framework. In Special Issue on Resources for Graph Data and Knowledge. Transactions on Graph Data and Knowledge (TGDK), Volume 2, Issue 2, pp. 5:1-5:54, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@Article{skjaeveland_et_al:TGDK.2.2.5,
  author =	{Skj{\ae}veland, Martin Georg and Karlsen, Leif Harald},
  title =	{{The Reasonable Ontology Templates Framework}},
  journal =	{Transactions on Graph Data and Knowledge},
  pages =	{5:1--5:54},
  ISSN =	{2942-7517},
  year =	{2024},
  volume =	{2},
  number =	{2},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/TGDK.2.2.5},
  URN =		{urn:nbn:de:0030-drops-225896},
  doi =		{10.4230/TGDK.2.2.5},
  annote =	{Keywords: Ontology engineering, Ontology design patterns, Template mechanism, Macros}
}

Document

DOI: 10.4230/OASIcs.SynCoP.2015.77

Parametric Verification of Weighted Systems

Authors: Peter Christoffersen, Mikkel Hansen, Anders Mariegaard, Julian Trier Ringsmose, Kim Guldstrand Larsen, and Radu Mardare

Published in: OASIcs, Volume 44, 2nd International Workshop on Synthesis of Complex Parameters (SynCoP'15) (2015)

Abstract

This paper addresses the problem of parametric model checking for weighted transition systems. We consider transition systems labelled with linear equations over a set of parameters and we use them to provide semantics for a parametric version of weighted CTL where the until and next operators are themselves indexed with linear equations. The parameters change the model-checking problem into a problem of computing a linear system of inequalities that characterizes the parameters that guarantee the satisfiability. To address this problem, we use parametric dependency graphs (PDGs) and we propose a global update function that yields an assignment to each node in a PDG. For an iterative application of the function, we prove that a fixed point assignment to PDG nodes exists and the set of assignments constitutes a well-quasi ordering, thus ensuring that the fixed point assignment can be found after finitely many iterations. To demonstrate the utility of our technique, we have implemented a prototype tool that computes the constraints on parameters for model checking problems.

Cite as

Peter Christoffersen, Mikkel Hansen, Anders Mariegaard, Julian Trier Ringsmose, Kim Guldstrand Larsen, and Radu Mardare. Parametric Verification of Weighted Systems. In 2nd International Workshop on Synthesis of Complex Parameters (SynCoP'15). Open Access Series in Informatics (OASIcs), Volume 44, pp. 77-90, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@InProceedings{christoffersen_et_al:OASIcs.SynCoP.2015.77,
  author =	{Christoffersen, Peter and Hansen, Mikkel and Mariegaard, Anders and Ringsmose, Julian Trier and Larsen, Kim Guldstrand and Mardare, Radu},
  title =	{{Parametric Verification of Weighted Systems}},
  booktitle =	{2nd International Workshop on Synthesis of Complex Parameters (SynCoP'15)},
  pages =	{77--90},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-82-8},
  ISSN =	{2190-6807},
  year =	{2015},
  volume =	{44},
  editor =	{Andr\'{e}, \'{E}tienne and Frehse, Goran},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.SynCoP.2015.77},
  URN =		{urn:nbn:de:0030-drops-56115},
  doi =		{10.4230/OASIcs.SynCoP.2015.77},
  annote =	{Keywords: parametric weighted transition systems, parametric weighted CTL, parametric model checking, well-quasi ordering, tool}
}

9 Search Results for "Hansen, Mikkel"

Path-Reporting Distance Oracles for Vertex-Labeled Graphs

Abstract

Cite as

Faster Dynamic 2-Edge Connectivity in Directed Graphs

Abstract

Cite as

Going Beyond Surfaces in Diameter Approximation

Abstract

Cite as

Efficient Contractions of Dynamic Graphs - With Applications

Abstract

Cite as

Higher Connectivity in Directed Graphs (Invited Talk)

Abstract

Cite as

On-The-Fly Verification: Advancements in Dependency Graphs (Invited Talk)

Abstract

Cite as

Faster Construction of a Planar Distance Oracle with Õ(1) Query Time

Abstract

Cite as

The Reasonable Ontology Templates Framework

Abstract

Cite as

Parametric Verification of Weighted Systems

Abstract

Cite as

Thanks for your feedback!

Could not send message