11 Search Results for "Duan, Ran"

Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2022.109
Faster Cut-Equivalent Trees in Simple Graphs

Authors: Tianyi Zhang

Published in: LIPIcs, Volume 229, 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)

Abstract
Let G = (V, E) be an undirected connected simple graph on n vertices. A cut-equivalent tree of G is an edge-weighted tree on the same vertex set V, such that for any pair of vertices s, t ∈ V, the minimum (s, t)-cut in the tree is also a minimum (s, t)-cut in G, and these two cuts have the same cut value. In a recent paper [Abboud, Krauthgamer and Trabelsi, STOC 2021], the authors propose the first subcubic time algorithm for constructing a cut-equivalent tree. More specifically, their algorithm has Õ(n^{2.5}) running time. Later on, this running time was significantly improved to n^{2+o(1)} by two independent works [Abboud, Krauthgamer and Trabelsi, FOCS 2021] and [Li, Panigrahi, Saranurak, FOCS 2021], and then to (m+n^{1.9})^{1+o(1)} by [Abboud, Krauthgamer and Trabelsi, SODA 2022]. In this paper, we improve the running time to Õ(n²) graphs if near-linear time max-flow algorithms exist, or Õ(n^{17/8}) using the currently fastest max-flow algorithm. Although our algorithm is slower than previous works, the runtime bound becomes better by a sub-polynomial factor in dense simple graphs when assuming near-linear time max-flow algorithms.
Cite as

Tianyi Zhang. Faster Cut-Equivalent Trees in Simple Graphs. In 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 229, pp. 109:1-109:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{zhang:LIPIcs.ICALP.2022.109,
  author =	{Zhang, Tianyi},
  title =	{{Faster Cut-Equivalent Trees in Simple Graphs}},
  booktitle =	{49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)},
  pages =	{109:1--109:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-235-8},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{229},
  editor =	{Boja\'{n}czyk, Miko{\l}aj and Merelli, Emanuela and Woodruff, David P.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2022.109},
  URN =		{urn:nbn:de:0030-drops-164507},
  doi =		{10.4230/LIPIcs.ICALP.2022.109},
  annote =	{Keywords: graph algorithms, minimum cuts, max-flow}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2021.76
Constructing a Distance Sensitivity Oracle in O(n^2.5794 M) Time

Authors: Yong Gu and Hanlin Ren

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

Abstract
We continue the study of distance sensitivity oracles (DSOs). Given a directed graph G with n vertices and edge weights in {1, 2, … , M}, we want to build a data structure such that given any source vertex u, any target vertex v, and any failure f (which is either a vertex or an edge), it outputs the length of the shortest path from u to v not going through f. Our main result is a DSO with preprocessing time O(n^2.5794 M) and constant query time. Previously, the best preprocessing time of DSOs for directed graphs is O(n^2.7233 M), and even in the easier case of undirected graphs, the best preprocessing time is O(n^2.6865 M) [Ren, ESA 2020]. One drawback of our DSOs, though, is that it only supports distance queries but not path queries. Our main technical ingredient is an algorithm that computes the inverse of a degree-d polynomial matrix (i.e. a matrix whose entries are degree-d univariate polynomials) modulo x^r. The algorithm is adapted from [Zhou, Labahn and Storjohann, Journal of Complexity, 2015], and we replace some of its intermediate steps with faster rectangular matrix multiplication algorithms. We also show how to compute unique shortest paths in a directed graph with edge weights in {1, 2, … , M}, in O(n^2.5286 M) time. This algorithm is crucial in the preprocessing algorithm of our DSO. Our solution improves the O(n^2.6865 M) time bound in [Ren, ESA 2020], and matches the current best time bound for computing all-pairs shortest paths.
Cite as

Yong Gu and Hanlin Ren. Constructing a Distance Sensitivity Oracle in O(n^2.5794 M) Time. In 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 198, pp. 76:1-76:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{gu_et_al:LIPIcs.ICALP.2021.76,
  author =	{Gu, Yong and Ren, Hanlin},
  title =	{{Constructing a Distance Sensitivity Oracle in O(n^2.5794 M) Time}},
  booktitle =	{48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)},
  pages =	{76:1--76: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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2021.76},
  URN =		{urn:nbn:de:0030-drops-141450},
  doi =		{10.4230/LIPIcs.ICALP.2021.76},
  annote =	{Keywords: graph theory, shortest paths, distance sensitivity oracles}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2021.114
Deterministic Maximum Flows in Simple Graphs

Authors: Tianyi Zhang

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

Abstract
In this paper we are interested in deterministically computing maximum flows in undirected simple graphs where edges have unit capacities. When the input graph has n vertices and m edges, and the maximum flow is known to be upper bounded by τ as prior knowledge, our algorithm has running time Õ(m + n^{5/3}τ^{1/2}); in the extreme case where τ = Θ(n), our algorithm has running time Õ(n^{2.17}). This always improves upon the previous best deterministic upper bound Õ(n^{9/4}τ^{1/8}) by [Duan, 2013]. Furthermore, when τ ≥ n^{0.67} our algorithm is faster than a classical upper bound of O(m + nτ^{3/2}) by [Karger and Levin, 1998].
Cite as

Tianyi Zhang. Deterministic Maximum Flows in Simple Graphs. In 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 198, pp. 114:1-114:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{zhang:LIPIcs.ICALP.2021.114,
  author =	{Zhang, Tianyi},
  title =	{{Deterministic Maximum Flows in Simple Graphs}},
  booktitle =	{48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)},
  pages =	{114:1--114:16},
  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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2021.114},
  URN =		{urn:nbn:de:0030-drops-141832},
  doi =		{10.4230/LIPIcs.ICALP.2021.114},
  annote =	{Keywords: graph algorithms, maximum flows, dynamic data structures}
}
Document
DOI: 10.4230/LIPIcs.ESA.2020.79
Improved Distance Sensitivity Oracles with Subcubic Preprocessing Time

Authors: Hanlin Ren

Published in: LIPIcs, Volume 173, 28th Annual European Symposium on Algorithms (ESA 2020)

Abstract
We consider the problem of building Distance Sensitivity Oracles (DSOs). Given a directed graph G = (V, E) with edge weights in {1, 2, … , M}, we need to preprocess it into a data structure, and answer the following queries: given vertices u,v,x ∈ V, output the length of the shortest path from u to v that does not go through x. Our main result is a simple DSO with Õ(n^2.7233 M²) preprocessing time and O(1) query time. Moreover, if the input graph is undirected, the preprocessing time can be improved to Õ(n^2.6865 M²). Our algorithms are randomized with correct probability ≥ 1-1/n^c, for a constant c that can be made arbitrarily large. Previously, there is a DSO with Õ(n^2.8729 M) preprocessing time and polylog(n) query time [Chechik and Cohen, STOC'20]. At the core of our DSO is the following observation from [Bernstein and Karger, STOC'09]: if there is a DSO with preprocessing time P and query time Q, then we can construct a DSO with preprocessing time P+Õ(Mn²)⋅ Q and query time O(1). (Here Õ(⋅) hides polylog(n) factors.)
Cite as

Hanlin Ren. Improved Distance Sensitivity Oracles with Subcubic Preprocessing Time. In 28th Annual European Symposium on Algorithms (ESA 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 173, pp. 79:1-79:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{ren:LIPIcs.ESA.2020.79,
  author =	{Ren, Hanlin},
  title =	{{Improved Distance Sensitivity Oracles with Subcubic Preprocessing Time}},
  booktitle =	{28th Annual European Symposium on Algorithms (ESA 2020)},
  pages =	{79:1--79:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-162-7},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{173},
  editor =	{Grandoni, Fabrizio and Herman, Grzegorz and Sanders, Peter},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2020.79},
  URN =		{urn:nbn:de:0030-drops-129450},
  doi =		{10.4230/LIPIcs.ESA.2020.79},
  annote =	{Keywords: Graph theory, Failure-prone structures}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2020.24
Roundtrip Spanners with (2k-1) Stretch

Authors: Ruoxu Cen, Ran Duan, and Yong Gu

Published in: LIPIcs, Volume 168, 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)

Abstract
A roundtrip spanner of a directed graph G is a subgraph of G preserving roundtrip distances approximately for all pairs of vertices. Despite extensive research, there is still a small stretch gap between roundtrip spanners in directed graphs and undirected graphs. For a directed graph with real edge weights in [1,W], we first propose a new deterministic algorithm that constructs a roundtrip spanner with (2k-1) stretch and O(k n^(1+1/k) log (nW)) edges for every integer k > 1, then remove the dependence of size on W to give a roundtrip spanner with (2k-1) stretch and O(k n^(1+1/k) log n) edges. While keeping the edge size small, our result improves the previous 2k+ε stretch roundtrip spanners in directed graphs [Roditty, Thorup, Zwick'02; Zhu, Lam'18], and almost matches the undirected (2k-1)-spanner with O(n^(1+1/k)) edges [Althöfer et al. '93] when k is a constant, which is optimal under Erdös conjecture.
Cite as

Ruoxu Cen, Ran Duan, and Yong Gu. Roundtrip Spanners with (2k-1) Stretch. In 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 168, pp. 24:1-24:11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{cen_et_al:LIPIcs.ICALP.2020.24,
  author =	{Cen, Ruoxu and Duan, Ran and Gu, Yong},
  title =	{{Roundtrip Spanners with (2k-1) Stretch}},
  booktitle =	{47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)},
  pages =	{24:1--24:11},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-138-2},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{168},
  editor =	{Czumaj, Artur and Dawar, Anuj and Merelli, Emanuela},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2020.24},
  URN =		{urn:nbn:de:0030-drops-124313},
  doi =		{10.4230/LIPIcs.ICALP.2020.24},
  annote =	{Keywords: Graph theory, Deterministic algorithm, Roundtrip spanners}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2020.41
A Scaling Algorithm for Weighted f-Factors in General Graphs

Authors: Ran Duan, Haoqing He, and Tianyi Zhang

Published in: LIPIcs, Volume 168, 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)

Abstract
We study the maximum weight perfect f-factor problem on any general simple graph G = (V,E,ω) with positive integral edge weights w, and n = |V|, m = |E|. When we have a function f:V → ℕ_+ on vertices, a perfect f-factor is a generalized matching so that every vertex u is matched to exactly f(u) different edges. The previous best results on this problem have running time O(m f(V)) [Gabow 2018] or Õ(W(f(V))^2.373)) [Gabow and Sankowski 2013], where W is the maximum edge weight, and f(V) = ∑_{u ∈ V}f(u). In this paper, we present a scaling algorithm for this problem with running time Õ(mn^{2/3} log W). Previously this bound is only known for bipartite graphs [Gabow and Tarjan 1989]. The advantage is that the running time is independent of f(V), and consequently it breaks the Ω(mn) barrier for large f(V) even for the unweighted f-factor problem in general graphs.
Cite as

Ran Duan, Haoqing He, and Tianyi Zhang. A Scaling Algorithm for Weighted f-Factors in General Graphs. In 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 168, pp. 41:1-41:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{duan_et_al:LIPIcs.ICALP.2020.41,
  author =	{Duan, Ran and He, Haoqing and Zhang, Tianyi},
  title =	{{A Scaling Algorithm for Weighted f-Factors in General Graphs}},
  booktitle =	{47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)},
  pages =	{41:1--41:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-138-2},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{168},
  editor =	{Czumaj, Artur and Dawar, Anuj and Merelli, Emanuela},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2020.41},
  URN =		{urn:nbn:de:0030-drops-124487},
  doi =		{10.4230/LIPIcs.ICALP.2020.41},
  annote =	{Keywords: Scaling Algorithm, f-Factors, General Graphs}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2019.48
Faster Algorithms for All Pairs Non-Decreasing Paths Problem

Authors: Ran Duan, Ce Jin, and Hongxun Wu

Published in: LIPIcs, Volume 132, 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)

Abstract
In this paper, we present an improved algorithm for the All Pairs Non-decreasing Paths (APNP) problem on weighted simple digraphs, which has running time O~(n^{{3 + omega}/{2}}) = O~(n^{2.686}). Here n is the number of vertices, and omega < 2.373 is the exponent of time complexity of fast matrix multiplication [Williams 2012, Le Gall 2014]. This matches the current best upper bound for (max, min)-matrix product [Duan, Pettie 2009] which is reducible to APNP. Thus, further improvement for APNP will imply a faster algorithm for (max, min)-matrix product. The previous best upper bound for APNP on weighted digraphs was O~(n^{1/2(3 + {3 - omega}/{omega + 1} + omega)}) = O~(n^{2.78}) [Duan, Gu, Zhang 2018]. We also show an O~(n^2) time algorithm for APNP in undirected simple graphs which also reaches optimal within logarithmic factors.
Cite as

Ran Duan, Ce Jin, and Hongxun Wu. Faster Algorithms for All Pairs Non-Decreasing Paths Problem. In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 132, pp. 48:1-48:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{duan_et_al:LIPIcs.ICALP.2019.48,
  author =	{Duan, Ran and Jin, Ce and Wu, Hongxun},
  title =	{{Faster Algorithms for All Pairs Non-Decreasing Paths Problem}},
  booktitle =	{46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)},
  pages =	{48:1--48:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-109-2},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{132},
  editor =	{Baier, Christel and Chatzigiannakis, Ioannis and Flocchini, Paola and Leonardi, Stefano},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2019.48},
  URN =		{urn:nbn:de:0030-drops-106241},
  doi =		{10.4230/LIPIcs.ICALP.2019.48},
  annote =	{Keywords: graph optimization, matrix multiplication, non-decreasing paths}
}
Document
DOI: 10.4230/LIPIcs.ICALP.2018.42
Approximating All-Pair Bounded-Leg Shortest Path and APSP-AF in Truly-Subcubic Time

Authors: Ran Duan and Hanlin Ren

Published in: LIPIcs, Volume 107, 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)

Abstract
In the bounded-leg shortest path (BLSP) problem, we are given a weighted graph G with nonnegative edge lengths, and we want to answer queries of the form "what's the shortest path from u to v, where only edges of length <=L are considered?". A more general problem is the APSP-AF (all-pair shortest path for all flows) problem, in which each edge has two weights - a length d and a capacity f, and a query asks about the shortest path from u to v where only edges of capacity >= f are considered. In this article we give an O~(n^{(omega+3)/2}epsilon^{-3/2}log W) time algorithm to compute a data structure that answers APSP-AF queries in O(log(epsilon^{-1}log (nW))) time and achieves (1+epsilon)-approximation, where omega < 2.373 is the exponent of time complexity of matrix multiplication, W is the upper bound of integer edge lengths, and n is the number of vertices. This is the first truly-subcubic time algorithm for these problems on dense graphs. Our algorithm utilizes the O(n^{(omega+3)/2}) time max-min product algorithm [Duan and Pettie 2009]. Since the all-pair bottleneck path (APBP) problem, which is equivalent to max-min product, can be seen as all-pair reachability for all flow, our approach indeed shows that these problems are almost equivalent in the approximation sense.
Cite as

Ran Duan and Hanlin Ren. Approximating All-Pair Bounded-Leg Shortest Path and APSP-AF in Truly-Subcubic Time. In 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 107, pp. 42:1-42:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{duan_et_al:LIPIcs.ICALP.2018.42,
  author =	{Duan, Ran and Ren, Hanlin},
  title =	{{Approximating All-Pair Bounded-Leg Shortest Path and APSP-AF in Truly-Subcubic Time}},
  booktitle =	{45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)},
  pages =	{42:1--42:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-076-7},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{107},
  editor =	{Chatzigiannakis, Ioannis and Kaklamanis, Christos and Marx, D\'{a}niel and Sannella, Donald},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2018.42},
  URN =		{urn:nbn:de:0030-drops-90467},
  doi =		{10.4230/LIPIcs.ICALP.2018.42},
  annote =	{Keywords: Graph Theory, Approximation Algorithms, Combinatorial Optimization}
}
Document
DOI: 10.4230/LIPIcs.ICALP.2018.43
Single-Source Bottleneck Path Algorithm Faster than Sorting for Sparse Graphs

Authors: Ran Duan, Kaifeng Lyu, and Yuanhang Xie

Published in: LIPIcs, Volume 107, 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)

Abstract
In a directed graph G=(V,E) with a capacity on every edge, a bottleneck path (or widest path) between two vertices is a path maximizing the minimum capacity of edges in the path. For the single-source all-destination version of this problem in directed graphs, the previous best algorithm runs in O(m+n log n) (m=|E| and n=|V|) time, by Dijkstra search with Fibonacci heap [Fredman and Tarjan 1987]. We improve this time bound to O(m sqrt{log n}+sqrt{mn log n log log n}), which is O(n sqrt{log n log log n}) when m=O(n), thus it is the first algorithm which breaks the time bound of classic Fibonacci heap when m=o(n sqrt{log n}). It is a Las-Vegas randomized approach. By contrast, the s-t bottleneck path has algorithm with running time O(m beta(m,n)) [Chechik et al. 2016], where beta(m,n)=min{k >= 1: log^{(k)}n <= m/n}.
Cite as

Ran Duan, Kaifeng Lyu, and Yuanhang Xie. Single-Source Bottleneck Path Algorithm Faster than Sorting for Sparse Graphs. In 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 107, pp. 43:1-43:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{duan_et_al:LIPIcs.ICALP.2018.43,
  author =	{Duan, Ran and Lyu, Kaifeng and Xie, Yuanhang},
  title =	{{Single-Source Bottleneck Path Algorithm Faster than Sorting for Sparse Graphs}},
  booktitle =	{45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)},
  pages =	{43:1--43:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-076-7},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{107},
  editor =	{Chatzigiannakis, Ioannis and Kaklamanis, Christos and Marx, D\'{a}niel and Sannella, Donald},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2018.43},
  URN =		{urn:nbn:de:0030-drops-90475},
  doi =		{10.4230/LIPIcs.ICALP.2018.43},
  annote =	{Keywords: Graph Algorithm, Bottleneck Path, Combinatorial Optimization}
}
Document
DOI: 10.4230/LIPIcs.ICALP.2018.44
Improved Time Bounds for All Pairs Non-decreasing Paths in General Digraphs

Authors: Ran Duan, Yong Gu, and Le Zhang

Published in: LIPIcs, Volume 107, 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)

Abstract
We present improved algorithms for solving the All Pairs Non-decreasing Paths (APNP) problem on weighted digraphs. Currently, the best upper bound on APNP is O~(n^{(9+omega)/4})=O(n^{2.844}), obtained by Vassilevska Williams [TALG 2010 and SODA'08], where omega<2.373 is the usual exponent of matrix multiplication. Our first algorithm improves the time bound to O~(n^{2+omega/3})=O(n^{2.791}). The algorithm determines, for every pair of vertices s, t, the minimum last edge weight on a non-decreasing path from s to t, where a non-decreasing path is a path on which the edge weights form a non-decreasing sequence. The algorithm proposed uses the combinatorial properties of non-decreasing paths. Also a slightly improved algorithm with running time O(n^{2.78}) is presented.
Cite as

Ran Duan, Yong Gu, and Le Zhang. Improved Time Bounds for All Pairs Non-decreasing Paths in General Digraphs. In 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 107, pp. 44:1-44:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{duan_et_al:LIPIcs.ICALP.2018.44,
  author =	{Duan, Ran and Gu, Yong and Zhang, Le},
  title =	{{Improved Time Bounds for All Pairs Non-decreasing Paths in General Digraphs}},
  booktitle =	{45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)},
  pages =	{44:1--44:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-076-7},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{107},
  editor =	{Chatzigiannakis, Ioannis and Kaklamanis, Christos and Marx, D\'{a}niel and Sannella, Donald},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2018.44},
  URN =		{urn:nbn:de:0030-drops-90487},
  doi =		{10.4230/LIPIcs.ICALP.2018.44},
  annote =	{Keywords: Graph algorithms, Matrix multiplication, Non-decreasing paths}
}
Document
DOI: 10.4230/LIPIcs.SWAT.2018.16
An Improved Algorithm for Incremental DFS Tree in Undirected Graphs

Authors: Lijie Chen, Ran Duan, Ruosong Wang, Hanrui Zhang, and Tianyi Zhang

Published in: LIPIcs, Volume 101, 16th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2018)

Abstract
Depth first search (DFS) tree is one of the most well-known data structures for designing efficient graph algorithms. Given an undirected graph G=(V,E) with n vertices and m edges, the textbook algorithm takes O(n+m) time to construct a DFS tree. In this paper, we study the problem of maintaining a DFS tree when the graph is undergoing incremental updates. Formally, we show: Given an arbitrary online sequence of edge or vertex insertions, there is an algorithm that reports a DFS tree in O(n) worst case time per operation, and requires O (min {m log n, n^2}) preprocessing time. Our result improves the previous O(n log^3 n) worst case update time algorithm by Baswana et al. [Baswana et al., 2016] and the O(n log n) time by Nakamura and Sadakane [Nakamura and Sadakane, 2017], and matches the trivial Omega(n) lower bound when it is required to explicitly output a DFS tree. Our result builds on the framework introduced in the breakthrough work by Baswana et al. [Baswana et al., 2016], together with a novel use of a tree-partition lemma by Duan and Zhang [Duan and Zhang, 2016], and the celebrated fractional cascading technique by Chazelle and Guibas [Chazelle and Guibas, 1986a; Chazelle and Guibas, 1986b].
Cite as

Lijie Chen, Ran Duan, Ruosong Wang, Hanrui Zhang, and Tianyi Zhang. An Improved Algorithm for Incremental DFS Tree in Undirected Graphs. In 16th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 101, pp. 16:1-16:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{chen_et_al:LIPIcs.SWAT.2018.16,
  author =	{Chen, Lijie and Duan, Ran and Wang, Ruosong and Zhang, Hanrui and Zhang, Tianyi},
  title =	{{An Improved Algorithm for Incremental DFS Tree in Undirected Graphs}},
  booktitle =	{16th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2018)},
  pages =	{16:1--16:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-068-2},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{101},
  editor =	{Eppstein, David},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2018.16},
  URN =		{urn:nbn:de:0030-drops-88427},
  doi =		{10.4230/LIPIcs.SWAT.2018.16},
  annote =	{Keywords: DFS tree, fractional cascading, fully dynamic algorithm}
}
  • Refine by Author
  • 7 Duan, Ran
  • 4 Zhang, Tianyi
  • 3 Gu, Yong
  • 3 Ren, Hanlin
  • 1 Cen, Ruoxu
  • Show More...

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

  • Refine by Keyword
  • 2 Combinatorial Optimization
  • 2 Graph theory
  • 2 graph algorithms
  • 1 Approximation Algorithms
  • 1 Bottleneck Path
  • Show More...

  • Refine by Type
  • 11 document

  • Refine by Publication Year
  • 4 2018
  • 3 2020
  • 2 2021
  • 1 2019
  • 1 2022

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact