Source author record

Liam Roditty

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

Data Structures and Algorithms Computational Geometry Computational Complexity Discrete Mathematics Distributed, Parallel, and Cluster Computing

Catalog footprint

Research overview

8works

5topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2019arXiv

Reachability Oracles for Directed Transmission Graphs

Let $P \subset \mathbb{R}^d$ be a set of $n$ points in $d$ dimensions such that each point $p \in P$ has an associated radius $r_p > 0$ . The transmission graph $G$ for $P$ is the directed graph with vertex set $P$ such that there is an edge from $p$ to $q$ if and only if $|pq| \leq r_p$ , for any $p, q \in P$ . A reachability oracle is a data structure that decides for any two vertices $p, q \in G$ whether $G$ has a path from $p$ to $q$ . The quality of the oracle is measured by the space requirement $S(n)$ , the query time $Q(n)$ , and the preprocessing time. For transmission graphs of one-dimensional point sets, we can construct in $O(n \log n)$ time an oracle with $Q(n) = O(1)$ and $S(n) = O(n)$ . For planar point sets, the ratio $Ψ$ between the largest and the smallest associated radius turns out to be an important parameter. We present three data structures whose quality depends on $Ψ$ : the first works only for $Ψ< \sqrt{3}$ and achieves $Q(n) = O(1)$ with $S(n) = O(n)$ and preprocessing time $O(n\log n)$ ; the second data structure gives $Q(n) = O(Ψ^3 \sqrt{n})$ and $S(n) = O(Ψ^3 n^{3/2})$ ; the third data structure is randomized with $Q(n) = O(n^{2/3}\log^{1/3} Ψ\log^{2/3} n)$ and $S(n) = O(n^{5/3}\log^{1/3} Ψ\log^{2/3} n)$ and answers queries correctly with high probability.

preprint2014arXiv

New routing techniques and their applications

Let $G=(V,E)$ be an undirected graph with $n$ vertices and $m$ edges. We obtain the following new routing schemes: - A routing scheme for unweighted graphs that uses $\tilde O(\frac{1}ε n^{2/3})$ space at each vertex and $\tilde O(1/ε)$ -bit headers, to route a message between any pair of vertices $u,v\in V$ on a $(2 + ε,1)$ -stretch path, i.e., a path of length at most $(2+ε)\cdot d(u,v)+1$ . This should be compared to the $(2,1)$ -stretch and $\tilde O(n^{5/3})$ space distance oracle of Patrascu and Roditty [FOCS'10 and SIAM J. Comput. 2014] and to the $(2,1)$ -stretch routing scheme of Abraham and Gavoille [DISC'11] that uses $\tilde O( n^{3/4})$ space at each vertex. - A routing scheme for weighted graphs with normalized diameter $D$ , that uses $\tilde O(\frac{1}ε n^{1/3}\log D)$ space at each vertex and $\tilde O(\frac{1}ε\log D)$ -bit headers, to route a message between any pair of vertices on a $(5+ε)$ -stretch path. This should be compared to the $5$ -stretch and $\tilde O(n^{4/3})$ space distance oracle of Thorup and Zwick [STOC'01 and J. ACM. 2005] and to the $7$ -stretch routing scheme of Thorup and Zwick [SPAA'01] that uses $\tilde O( n^{1/3})$ space at each vertex. Since a $5$ -stretch routing scheme must use tables of $Ω( n^{1/3})$ space our result is almost tight. - For an integer $\ell>1$ , a routing scheme for unweighted graphs that uses $\tilde O(\ell\frac{1}ε n^{\ell/(2\ell \pm 1)})$ space at each vertex and $\tilde O(\frac{1}ε)$ -bit headers, to route a message between any pair of vertices on a $(3\pm2/\ell+ε,2)$ -stretch path. - A routing scheme for weighted graphs, that uses $\tilde O(\frac{1}εn^{1/k}\log D)$ space at each vertex and $\tilde O(\frac{1}ε\log D)$ -bit headers, to route a message between any pair of vertices on a $(4k-7+ε)$ -stretch path.

preprint2013arXiv

A Labeling Approach to Incremental Cycle Detection

In the \emph{incremental cycle detection} problem arcs are added to a directed acyclic graph and the algorithm has to report if the new arc closes a cycle. One seeks to minimize the total time to process the entire sequence of arc insertions, or until a cycle appears. In a recent breakthrough, Bender, Fineman, Gilbert and Tarjan \cite{BeFiGiTa11} presented two different algorithms, with time complexity $O(n^2 \log n)$ and $O(m \cdot \min \{m^{1/2}, n^{2/3} \})$ , respectively. In this paper we introduce a new technique for incremental cycle detection that allows us to obtain both bounds (up to a logarithmic factor). Furthermore, our approach seems more amiable for distributed implementation.

preprint2013arXiv

Finding the Minimum-Weight k-Path

Given a weighted $n$ -vertex graph $G$ with integer edge-weights taken from a range $[-M,M]$ , we show that the minimum-weight simple path visiting $k$ vertices can be found in time $\tilde{O}(2^k \poly(k) M n^ω) = O^*(2^k M)$. If the weights are reals in $[1,M]$ , we provide a $(1+\varepsilon)$ -approximation which has a running time of $\tilde{O}(2^k \poly(k) n^ω(\log\log M + 1/\varepsilon))$. For the more general problem of $k$ -tree, in which we wish to find a minimum-weight copy of a $k$ -node tree $T$ in a given weighted graph $G$ , under the same restrictions on edge weights respectively, we give an exact solution of running time $\tilde{O}(2^k \poly(k) M n^3) $ and a $(1+\varepsilon)$ -approximate solution of running time $\tilde{O}(2^k \poly(k) n^3(\log\log M + 1/\varepsilon))$. All of the above algorithms are randomized with a polynomially-small error probability.

preprint2012arXiv

Approximating the diameter of a graph

In this paper we consider the fundamental problem of approximating the diameter $D$ of directed or undirected graphs. In a seminal paper, Aingworth, Chekuri, Indyk and Motwani [SIAM J. Comput. 1999] presented an algorithm that computes in $\Ot(m\sqrt n + n^2)$ time an estimate $\hat{D}$ for the diameter of an $n$ -node, $m$ -edge graph, such that $\lfloor 2/3 D \rfloor \leq \hat{D} \leq D$ . In this paper we present an algorithm that produces the same estimate in $\Ot(m\sqrt n)$ expected running time. We then provide strong evidence that a better approximation may be hard to obtain if we insist on an $O(m^{2-\eps})$ running time. In particular, we show that if there is some constant $\eps>0$ so that there is an algorithm for undirected unweighted graphs that runs in $O(m^{2-\eps})$ time and produces an approximation $\hat{D}$ such that $ (2/3+\eps) D \leq \hat{D} \leq D$, then SAT for CNF formulas on $n$ variables can be solved in $O^{*}((2-δ)^{n})$ time for some constant $δ>0$ , and the strong exponential time hypothesis of [Impagliazzo, Paturi, Zane JCSS'01] is false. Motivated by this somewhat negative result, we study whether it is possible to obtain a better approximation for specific cases. For unweighted directed or undirected graphs, we show that if $D=3h+z$ , where $h\geq 0$ and $z\in {0,1,2}$ , then it is possible to report in $\tilde{O}(\min{m^{2/3} n^{4/3},m^{2-1/(2h+3)}})$ time an estimate $\hat{D}$ such that $2h+z \leq \hat{D}\leq D$ , thus giving a better than 3/2 approximation whenever $z\neq 0$ . This is significant for constant values of $D$ which is exactly when the diameter approximation problem is hardest to solve. For the case of unweighted undirected graphs we present an $\tilde{O}(m^{2/3} n^{4/3})$ time algorithm that reports an estimate $\hat{D}$ such that $\lfloor 4D/5\rfloor \leq \hat{D}\leq D$ .

preprint2011arXiv

Minimum Weight Cycles and Triangles: Equivalences and Algorithms

We consider the fundamental algorithmic problem of finding a cycle of minimum weight in a weighted graph. In particular, we show that the minimum weight cycle problem in an undirected n-node graph with edge weights in {1,...,M} or in a directed n-node graph with edge weights in {-M,..., M} and no negative cycles can be efficiently reduced to finding a minimum weight triangle in an Theta(n)-node undirected graph with weights in {1,...,O(M)}. Roughly speaking, our reductions imply the following surprising phenomenon: a minimum cycle with an arbitrary number of weighted edges can be "encoded" using only three edges within roughly the same weight interval! This resolves a longstanding open problem posed by Itai and Rodeh [SIAM J. Computing 1978 and STOC'77]. A direct consequence of our efficient reductions are O (Mn^{omega})-time algorithms using fast matrix multiplication (FMM) for finding a minimum weight cycle in both undirected graphs with integral weights from the interval [1,M] and directed graphs with integral weights from the interval [-M,M]. The latter seems to reveal a strong separation between the all pairs shortest paths (APSP) problem and the minimum weight cycle problem in directed graphs as the fastest known APSP algorithm has a running time of O(M^{0.681}n^{2.575}) by Zwick [J. ACM 2002]. In contrast, when only combinatorial algorithms are allowed (that is, without FMM) the only known solution to minimum weight cycle is by computing APSP. Interestingly, any separation between the two problems in this case would be an amazing breakthrough as by a recent paper by Vassilevska W. and Williams [FOCS'10], any O(n^{3-eps})-time algorithm (eps>0) for minimum weight cycle immediately implies a O(n^{3-delta})-time algorithm (delta>0) for APSP.

preprint2010arXiv

Fast, precise and dynamic distance queries

We present an approximate distance oracle for a point set S with n points and doubling dimension λ. For every ε>0, the oracle supports (1+ε)-approximate distance queries in (universal) constant time, occupies space [ε^{-O(λ)} + 2^{O(λ log λ)}]n, and can be constructed in [2^{O(λ)} log3 n + ε^{-O(λ)} + 2^{O(λ log λ)}]n expected time. This improves upon the best previously known constructions, presented by Har-Peled and Mendel. Furthermore, the oracle can be made fully dynamic with expected O(1) query time and only 2^{O(λ)} log n + ε^{-O(λ)} + 2^{O(λ log λ)} update time. This is the first fully dynamic (1+ε)-distance oracle.

preprint2010arXiv

Relaxed spanners for directed disk graphs

Let $(V,δ)$ be a finite metric space, where $V$ is a set of $n$ points and $δ$ is a distance function defined for these points. Assume that $(V,δ)$ has a constant doubling dimension $d$ and assume that each point $p\in V$ has a disk of radius $r(p)$ around it. The disk graph that corresponds to $V$ and $r(\cdot)$ is a \emph{directed} graph $I(V,E,r)$ , whose vertices are the points of $V$ and whose edge set includes a directed edge from $p$ to $q$ if $δ(p,q)\leq r(p)$ . In \cite{PeRo08} we presented an algorithm for constructing a $(1+\eps)$-spanner of size $O(n/\eps^d \log M)$, where $M$ is the maximal radius $r(p)$ . The current paper presents two results. The first shows that the spanner of \cite{PeRo08} is essentially optimal, i.e., for metrics of constant doubling dimension it is not possible to guarantee a spanner whose size is independent of $M$ . The second result shows that by slightly relaxing the requirements and allowing a small perturbation of the radius assignment, considerably better spanners can be constructed. In particular, we show that if it is allowed to use edges of the disk graph $I(V,E,r_{1+\eps})$, where $r_{1+\eps}(p) = (1+\eps)\cdot r(p)$ for every $p\in V$ , then it is possible to get a $(1+\eps)$-spanner of size $O(n/\eps^d)$ for $I(V,E,r)$ . Our algorithm is simple and can be implemented efficiently.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.