10 Search Results for "Wulff-Nilsen, Christian"


Document
Dynamic Time Warping Under Translation: Approximation Guided by Space-Filling Curves

Authors: Karl Bringmann, Sándor Kisfaludi‑Bak, Marvin Künnemann, Dániel Marx, and André Nusser

Published in: LIPIcs, Volume 224, 38th International Symposium on Computational Geometry (SoCG 2022)


Abstract
The Dynamic Time Warping (DTW) distance is a popular measure of similarity for a variety of sequence data. For comparing polygonal curves π, σ in ℝ^d, it provides a robust, outlier-insensitive alternative to the Fréchet distance. However, like the Fréchet distance, the DTW distance is not invariant under translations. Can we efficiently optimize the DTW distance of π and σ under arbitrary translations, to compare the curves' shape irrespective of their absolute location? There are surprisingly few works in this direction, which may be due to its computational intricacy: For the Euclidean norm, this problem contains as a special case the geometric median problem, which provably admits no exact algebraic algorithm (that is, no algorithm using only addition, multiplication, and k-th roots). We thus investigate exact algorithms for non-Euclidean norms as well as approximation algorithms for the Euclidean norm. For the L₁ norm in ℝ^d, we provide an 𝒪(n^{2(d+1)})-time algorithm, i.e., an exact polynomial-time algorithm for constant d. Here and below, n bounds the curves' complexities. For the Euclidean norm in ℝ², we show that a simple problem-specific insight leads to a (1+ε)-approximation in time 𝒪(n³/ε²). We then show how to obtain a subcubic 𝒪̃(n^{2.5}/ε²) time algorithm with significant new ideas; this time comes close to the well-known quadratic time barrier for computing DTW for fixed translations. Technically, the algorithm is obtained by speeding up repeated DTW distance estimations using a dynamic data structure for maintaining shortest paths in weighted planar digraphs. Crucially, we show how to traverse a candidate set of translations using space-filling curves in a way that incurs only few updates to the data structure. We hope that our results will facilitate the use of DTW under translation both in theory and practice, and inspire similar algorithmic approaches for related geometric optimization problems.

Cite as

Karl Bringmann, Sándor Kisfaludi‑Bak, Marvin Künnemann, Dániel Marx, and André Nusser. Dynamic Time Warping Under Translation: Approximation Guided by Space-Filling Curves. In 38th International Symposium on Computational Geometry (SoCG 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 224, pp. 20:1-20:17, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)


Copy BibTex To Clipboard

@InProceedings{bringmann_et_al:LIPIcs.SoCG.2022.20,
  author =	{Bringmann, Karl and Kisfaludi‑Bak, S\'{a}ndor and K\"{u}nnemann, Marvin and Marx, D\'{a}niel and Nusser, Andr\'{e}},
  title =	{{Dynamic Time Warping Under Translation: Approximation Guided by Space-Filling Curves}},
  booktitle =	{38th International Symposium on Computational Geometry (SoCG 2022)},
  pages =	{20:1--20:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-227-3},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{224},
  editor =	{Goaoc, Xavier and Kerber, Michael},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2022.20},
  URN =		{urn:nbn:de:0030-drops-160287},
  doi =		{10.4230/LIPIcs.SoCG.2022.20},
  annote =	{Keywords: Dynamic Time Warping, Sequence Similarity Measures}
}
Document
Near-Optimal Distance Oracles for Vertex-Labeled Planar Graphs

Authors: Jacob Evald, Viktor Fredslund-Hansen, and Christian Wulff-Nilsen

Published in: LIPIcs, Volume 212, 32nd International Symposium on Algorithms and Computation (ISAAC 2021)


Abstract
Given an undirected n-vertex planar graph G = (V,E,ω) with non-negative edge weight function ω:E → ℝ and given an assigned label to each vertex, a vertex-labeled distance oracle is a data structure which for any query consisting of a vertex u and a label λ reports the shortest path distance from u to the nearest vertex with label λ. We show that if there is a distance oracle for undirected n-vertex planar graphs with non-negative edge weights using s(n) space and with query time q(n), then there is a vertex-labeled distance oracle with Õ(s(n)) space and Õ(q(n)) query time. Using the state-of-the-art distance oracle of Long and Pettie [Long and Pettie, 2021], our construction produces a vertex-labeled distance oracle using n^{1+o(1)} space and query time Õ(1) at one extreme, Õ(n) space and n^o(1) query time at the other extreme, as well as such oracles for the full tradeoff between space and query time obtained in their paper. This is the first non-trivial exact vertex-labeled distance oracle for planar graphs and, to our knowledge, for any interesting graph class other than trees.

Cite as

Jacob Evald, Viktor Fredslund-Hansen, and Christian Wulff-Nilsen. Near-Optimal Distance Oracles for Vertex-Labeled Planar Graphs. In 32nd International Symposium on Algorithms and Computation (ISAAC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 212, pp. 23:1-23:14, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021)


Copy BibTex To Clipboard

@InProceedings{evald_et_al:LIPIcs.ISAAC.2021.23,
  author =	{Evald, Jacob and Fredslund-Hansen, Viktor and Wulff-Nilsen, Christian},
  title =	{{Near-Optimal Distance Oracles for Vertex-Labeled Planar Graphs}},
  booktitle =	{32nd International Symposium on Algorithms and Computation (ISAAC 2021)},
  pages =	{23:1--23:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-214-3},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{212},
  editor =	{Ahn, Hee-Kap and Sadakane, Kunihiko},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2021.23},
  URN =		{urn:nbn:de:0030-drops-154566},
  doi =		{10.4230/LIPIcs.ISAAC.2021.23},
  annote =	{Keywords: distance oracle, vertex labels, color distance oracle, planar graph}
}
Document
Truly Subquadratic Exact Distance Oracles with Constant Query Time for Planar Graphs

Authors: Viktor Fredslund-Hansen, Shay Mozes, and Christian Wulff-Nilsen

Published in: LIPIcs, Volume 212, 32nd International Symposium on Algorithms and Computation (ISAAC 2021)


Abstract
We present a truly subquadratic size distance oracle for reporting, in constant time, the exact shortest-path distance between any pair of vertices of an undirected, unweighted planar graph G. For any ε > 0, our distance oracle requires O(n^{5/3+ε}) space and is capable of answering shortest-path distance queries exactly for any pair of vertices of G in worst-case time O(log (1/ε)). Previously no truly sub-quadratic size distance oracles with constant query time for answering exact shortest paths distance queries existed.

Cite as

Viktor Fredslund-Hansen, Shay Mozes, and Christian Wulff-Nilsen. Truly Subquadratic Exact Distance Oracles with Constant Query Time for Planar Graphs. In 32nd International Symposium on Algorithms and Computation (ISAAC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 212, pp. 25:1-25:12, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021)


Copy BibTex To Clipboard

@InProceedings{fredslundhansen_et_al:LIPIcs.ISAAC.2021.25,
  author =	{Fredslund-Hansen, Viktor and Mozes, Shay and Wulff-Nilsen, Christian},
  title =	{{Truly Subquadratic Exact Distance Oracles with Constant Query Time for Planar Graphs}},
  booktitle =	{32nd International Symposium on Algorithms and Computation (ISAAC 2021)},
  pages =	{25:1--25:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-214-3},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{212},
  editor =	{Ahn, Hee-Kap and Sadakane, Kunihiko},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2021.25},
  URN =		{urn:nbn:de:0030-drops-154586},
  doi =		{10.4230/LIPIcs.ISAAC.2021.25},
  annote =	{Keywords: distance oracle, planar graph, shortest paths, subquadratic}
}
Document
Track A: Algorithms, Complexity and Games
Decremental APSP in Unweighted Digraphs Versus an Adaptive Adversary

Authors: Jacob Evald, Viktor Fredslund-Hansen, Maximilian Probst Gutenberg, and Christian Wulff-Nilsen

Published in: LIPIcs, Volume 198, 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)


Abstract
Given an unweighted digraph G = (V,E), undergoing a sequence of edge deletions, with m = |E|, n = |V|, we consider the problem of maintaining all-pairs shortest paths (APSP). Whilst this problem has been studied in a long line of research [ACM'81, FOCS'99, FOCS'01, STOC'02, STOC'03, SWAT'04, STOC'13] and the problem of (1+ε)-approximate, weighted APSP was solved to near-optimal update time Õ(mn) by Bernstein [STOC'13], the problem has mainly been studied in the context of an oblivious adversary which fixes the update sequence before the algorithm is started. In this paper, we make significant progress on the problem for an adaptive adversary which can perform updates based on answers to previous queries: - We first present a deterministic data structure that maintains the exact distances with total update time Õ(n³). - We also present a deterministic data structure that maintains (1+ε)-approximate distance estimates with total update time Õ(√m n²/ε) which for sparse graphs is Õ(n^{2+1/2}/ε). - Finally, we present a randomized (1+ε)-approximate data structure which works against an adaptive adversary; its total update time is Õ(m^{2/3}n^{5/3} + n^{8/3}/(m^{1/3}ε²)) which for sparse graphs is Õ(n^{2+1/3}/ε²). Our exact data structure matches the total update time of the best randomized data structure by Baswana et al. [STOC'02] and maintains the distance matrix in near-optimal time. Our approximate data structures improve upon the best data structures against an adaptive adversary which have Õ(mn²) total update time [JACM'81, STOC'03].

Cite as

Jacob Evald, Viktor Fredslund-Hansen, Maximilian Probst Gutenberg, and Christian Wulff-Nilsen. Decremental APSP in Unweighted Digraphs Versus an Adaptive Adversary. In 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 198, pp. 64:1-64:20, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021)


Copy BibTex To Clipboard

@InProceedings{evald_et_al:LIPIcs.ICALP.2021.64,
  author =	{Evald, Jacob and Fredslund-Hansen, Viktor and Gutenberg, Maximilian Probst and Wulff-Nilsen, Christian},
  title =	{{Decremental APSP in Unweighted Digraphs Versus an Adaptive Adversary}},
  booktitle =	{48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)},
  pages =	{64:1--64:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-195-5},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{198},
  editor =	{Bansal, Nikhil and Merelli, Emanuela and Worrell, James},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2021.64},
  URN =		{urn:nbn:de:0030-drops-141337},
  doi =		{10.4230/LIPIcs.ICALP.2021.64},
  annote =	{Keywords: Dynamic Graph Algorithm, Data Structure, Shortest Paths}
}
Document
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
Fault Tolerant and Fully Dynamic DFS in Undirected Graphs: Simple Yet Efficient

Authors: Surender Baswana, Shiv Gupta, and Ayush Tulsyan

Published in: LIPIcs, Volume 138, 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)


Abstract
We present an algorithm for a fault tolerant Depth First Search (DFS) Tree in an undirected graph. This algorithm is drastically simpler than the current state-of-the-art algorithms for this problem, uses optimal space and optimal preprocessing time, and still achieves better time complexity. This algorithm also leads to a better time complexity for maintaining a DFS tree in a fully dynamic environment.

Cite as

Surender Baswana, Shiv Gupta, and Ayush Tulsyan. Fault Tolerant and Fully Dynamic DFS in Undirected Graphs: Simple Yet Efficient. In 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 138, pp. 65:1-65:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)


Copy BibTex To Clipboard

@InProceedings{baswana_et_al:LIPIcs.MFCS.2019.65,
  author =	{Baswana, Surender and Gupta, Shiv and Tulsyan, Ayush},
  title =	{{Fault Tolerant and Fully Dynamic DFS in Undirected Graphs: Simple Yet Efficient}},
  booktitle =	{44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)},
  pages =	{65:1--65:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-117-7},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{138},
  editor =	{Rossmanith, Peter and Heggernes, Pinar and Katoen, Joost-Pieter},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2019.65},
  URN =		{urn:nbn:de:0030-drops-110096},
  doi =		{10.4230/LIPIcs.MFCS.2019.65},
  annote =	{Keywords: Depth first search, DFS, Dynamic graph algorithms, Fault tolerant}
}
Document
Best Laid Plans of Lions and Men

Authors: Mikkel Abrahamsen, Jacob Holm, Eva Rotenberg, and Christian Wulff-Nilsen

Published in: LIPIcs, Volume 77, 33rd International Symposium on Computational Geometry (SoCG 2017)


Abstract
We answer the following question dating back to J.E. Littlewood (1885-1977): Can two lions catch a man in a bounded area with rectifiable lakes? The lions and the man are all assumed to be points moving with at most unit speed. That the lakes are rectifiable means that their boundaries are finitely long. This requirement is to avoid pathological examples where the man survives forever because any path to the lions is infinitely long. We show that the answer to the question is not always "yes", by giving an example of a region R in the plane where the man has a strategy to survive forever. R is a polygonal region with holes and the exterior and interior boundaries are pairwise disjoint, simple polygons. Our construction is the first truly two-dimensional example where the man can survive. Next, we consider the following game played on the entire plane instead of a bounded area: There is any finite number of unit speed lions and one fast man who can run with speed 1+epsilon for some value epsilon>0. Can the man always survive? We answer the question in the affirmative for any constant epsilon>0.

Cite as

Mikkel Abrahamsen, Jacob Holm, Eva Rotenberg, and Christian Wulff-Nilsen. Best Laid Plans of Lions and Men. In 33rd International Symposium on Computational Geometry (SoCG 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 77, pp. 6:1-6:16, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2017)


Copy BibTex To Clipboard

@InProceedings{abrahamsen_et_al:LIPIcs.SoCG.2017.6,
  author =	{Abrahamsen, Mikkel and Holm, Jacob and Rotenberg, Eva and Wulff-Nilsen, Christian},
  title =	{{Best Laid Plans of Lions and Men}},
  booktitle =	{33rd International Symposium on Computational Geometry (SoCG 2017)},
  pages =	{6:1--6:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-038-5},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{77},
  editor =	{Aronov, Boris and Katz, Matthew J.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2017.6},
  URN =		{urn:nbn:de:0030-drops-72053},
  doi =		{10.4230/LIPIcs.SoCG.2017.6},
  annote =	{Keywords: Lion and man game, Pursuit evasion game, Winning strategy}
}
Document
Near Optimal Adjacency Labeling Schemes for Power-Law Graphs

Authors: Casper Petersen, Noy Rotbart, Jakob Grue Simonsen, and Christian Wulff-Nilsen

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


Abstract
An adjacency labeling scheme labels the n nodes of a graph with bit strings in a way that allows, given the labels of two nodes, to determine adjacency based only on those bit strings. Though many graph families have been meticulously studied for this problem, a non-trivial labeling scheme for the important family of power-law graphs has yet to be obtained. This family is particularly useful for social and web networks as their underlying graphs are typically modelled as power-law graphs. Using simple strategies and a careful selection of a parameter, we show upper bounds for such labeling schemes of ~O(sqrt^{alpha}(n)) for power law graphs with coefficient alpha;, as well as nearly matching lower bounds. We also show two relaxations that allow for a label of logarithmic size, and extend the upper-bound technique to produce an improved distance labeling scheme for power-law graphs.

Cite as

Casper Petersen, Noy Rotbart, Jakob Grue Simonsen, and Christian Wulff-Nilsen. Near Optimal Adjacency Labeling Schemes for Power-Law Graphs. In 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 55, pp. 133:1-133:15, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2016)


Copy BibTex To Clipboard

@InProceedings{petersen_et_al:LIPIcs.ICALP.2016.133,
  author =	{Petersen, Casper and Rotbart, Noy and Simonsen, Jakob Grue and Wulff-Nilsen, Christian},
  title =	{{Near Optimal Adjacency Labeling Schemes for Power-Law Graphs}},
  booktitle =	{43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)},
  pages =	{133:1--133:15},
  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.133},
  URN =		{urn:nbn:de:0030-drops-62684},
  doi =		{10.4230/LIPIcs.ICALP.2016.133},
  annote =	{Keywords: Labeling schemes, Power-law graphs}
}
Document
All-Pairs Minimum Cuts in Near-Linear Time for Surface-Embedded Graphs

Authors: Glencora Borradaile, David Eppstein, Amir Nayyeri, and Christian Wulff-Nilsen

Published in: LIPIcs, Volume 51, 32nd International Symposium on Computational Geometry (SoCG 2016)


Abstract
For an undirected n-vertex graph G with non-negative edge-weights, we consider the following type of query: given two vertices s and t in G, what is the weight of a minimum st-cut in G? We solve this problem in preprocessing time O(n log^3 n) for graphs of bounded genus, giving the first sub-quadratic time algorithm for this class of graphs. Our result also improves by a logarithmic factor a previous algorithm by Borradaile, Sankowski and Wulff-Nilsen (FOCS 2010) that applied only to planar graphs. Our algorithm constructs a Gomory-Hu tree for the given graph, providing a data structure with space O(n) that can answer minimum-cut queries in constant time. The dependence on the genus of the input graph in our preprocessing time is 2^{O(g^2)}.

Cite as

Glencora Borradaile, David Eppstein, Amir Nayyeri, and Christian Wulff-Nilsen. All-Pairs Minimum Cuts in Near-Linear Time for Surface-Embedded Graphs. In 32nd International Symposium on Computational Geometry (SoCG 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 51, pp. 22:1-22:16, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2016)


Copy BibTex To Clipboard

@InProceedings{borradaile_et_al:LIPIcs.SoCG.2016.22,
  author =	{Borradaile, Glencora and Eppstein, David and Nayyeri, Amir and Wulff-Nilsen, Christian},
  title =	{{All-Pairs Minimum Cuts in Near-Linear Time for Surface-Embedded Graphs}},
  booktitle =	{32nd International Symposium on Computational Geometry (SoCG 2016)},
  pages =	{22:1--22:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-009-5},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{51},
  editor =	{Fekete, S\'{a}ndor and Lubiw, Anna},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2016.22},
  URN =		{urn:nbn:de:0030-drops-59149},
  doi =		{10.4230/LIPIcs.SoCG.2016.22},
  annote =	{Keywords: minimum cuts, surface-embedded graphs, Gomory-Hu tree}
}
Document
Optimal Decremental Connectivity in Planar Graphs

Authors: Jakub Lacki and Piotr Sankowski

Published in: LIPIcs, Volume 30, 32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015)


Abstract
We show an algorithm for dynamic maintenance of connectivity information in an undirected planar graph subject to edge deletions. Our algorithm may answer connectivity queries of the form 'Are vertices u and v connected with a path?' in constant time. The queries can be intermixed with any sequence of edge deletions, and the algorithm handles all updates in O(n) time. This results improves over previously known O(n \log n) time algorithm.

Cite as

Jakub Lacki and Piotr Sankowski. Optimal Decremental Connectivity in Planar Graphs. In 32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 30, pp. 608-621, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)


Copy BibTex To Clipboard

@InProceedings{lacki_et_al:LIPIcs.STACS.2015.608,
  author =	{Lacki, Jakub and Sankowski, Piotr},
  title =	{{Optimal Decremental Connectivity in Planar Graphs}},
  booktitle =	{32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015)},
  pages =	{608--621},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-78-1},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{30},
  editor =	{Mayr, Ernst W. and Ollinger, Nicolas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2015.608},
  URN =		{urn:nbn:de:0030-drops-49457},
  doi =		{10.4230/LIPIcs.STACS.2015.608},
  annote =	{Keywords: decremental connectivity, planar graphs, dynamic connectivity, algorithms}
}
  • Refine by Author
  • 7 Wulff-Nilsen, Christian
  • 3 Fredslund-Hansen, Viktor
  • 2 Evald, Jacob
  • 1 Abrahamsen, Mikkel
  • 1 Alstrup, Stephen
  • Show More...

  • Refine by Classification
  • 3 Theory of computation → Data structures design and analysis
  • 3 Theory of computation → Dynamic graph algorithms
  • 3 Theory of computation → Shortest paths
  • 2 Mathematics of computing → Graph algorithms
  • 1 Theory of computation → Computational geometry
  • Show More...

  • Refine by Keyword
  • 2 distance oracle
  • 2 planar graph
  • 1 DFS
  • 1 Data Structure
  • 1 Depth first search
  • Show More...

  • Refine by Type
  • 10 document

  • Refine by Publication Year
  • 3 2021
  • 2 2016
  • 2 2019
  • 1 2015
  • 1 2017
  • Show More...

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