wovepaper — the arXiv observatory

papers

Publications (34)

cs.CG2021

Stabbing Pairwise Intersecting Disks by Five Points

Sariel Har-Peled, Haim Kaplan, Wolfgang Mulzer +4

Suppose we are given a set $D$ of $n$ pairwise intersecting disks in the plane. A planar point set $P$ stabs $D$ if and only if each disk in $D$ conta…

cs.NI2025

Compact routing schemes in undirected and directed graphs

Avi Kadria, Liam Roditty

In this paper, we study the problem of compact routing schemes in weighted undirected and directed graphs. \textit{For weighted undirected graphs}, more than a decade ago, Chechik…

cs.DS2024

On the Space Usage of Approximate Distance Oracles with Sub-2 Stretch

Tsvi Kopelowitz, Ariel Korin, Liam Roditty

For an undirected unweighted graph G = (V, E) with n vertices and m edges, let d(u, v) denote the distance from u in V to v in V in G. An (alpha, beta)-stretch approximate distance…

cs.DS2010

Relaxed spanners for directed disk graphs

David Peleg, Liam Roditty

Let $(V, I^´)$ be a finite metric space, where $V$ is a set of $n$ points and $I^´$ is a distance function defined for these points. Assume that $(V, I^´)$ has a constant doubling dimen…

cs.DS2012

Approximating the diameter of a graph

Liam Roditty, Virginia Vassilevska Williams

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 [SIA…

cs.DS2014

New routing techniques and their applications

Liam Roditty, Roei Tov

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(\fra…

cs.DS2013

Finding the Minimum-Weight k-Path

Avinatan Hassidim, Orgad Keller, Moshe Lewenstein +1

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…

cs.DS2021

Towards Tight Approximation Bounds for Graph Diameter and Eccentricities

Arturs Backurs, Liam Roditty, Gilad Segal +2

Among the most important graph parameters is the Diameter, the largest distance between any two vertices. There are no known very efficient algorithms for computing the Diameter ex…

cs.DS2018

Approximating Cycles in Directed Graphs: Fast Algorithms for Girth and Roundtrip Spanners

Jakub Pachocki, Liam Roditty, Aaron Sidford +2

The girth of a graph, i.e. the length of its shortest cycle, is a fundamental graph parameter. Unfortunately all known algorithms for computing, even approximately, the girth and g…

cs.NI2008

SINR Diagrams: Towards Algorithmically Usable SINR Models of Wireless Networks

Chen Avin, Yuval Emek, Erez Kantor +3

The rules governing the availability and quality of connections in a wireless network are described by physical models such as the signal-to-interference & noise ratio (SINR) model…

cs.DS2026

New algorithms for girth and cycle detection

Liam Roditty, Plia Trabelsi

Let $G = (V, E)$ be an unweighted undirected graph with $n$ vertices and $m$ edges. Let $g$ be the girth of $G$ , that is, the length of a shortest cycle in $G$ . We present a randomize…

cs.DS2011

Minimum Weight Cycles and Triangles: Equivalences and Algorithms

Liam Roditty, Virginia Vassilevska Williams

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 undirec…

cs.DS2026

Tighter bounds for weighted and unweighted shortest cycle approximation

Avi Kadria, Liam Roditty, Virginia Vassilevska Williams

We study the problem of approximating the length of a shortest cycle in a given graph, known as the girth of the graph. The state-of-the-art approximation algorithms for unweighted…

cs.DS2008

Dynamic Connectivity: Connecting to Networks and Geometry

Timothy M. Chan, Mihai Patrascu, Liam Roditty

Dynamic connectivity is a well-studied problem, but so far the most compelling progress has been confined to the edge-update model: maintain an understanding of connectivity in an…

cs.CG2020

Spanners for Directed Transmission Graphs

Haim Kaplan, Wolfgang Mulzer, Liam Roditty +1

Let $P \subset R^{2}$ be a planar $n$ -point set such that each point $p \in P$ has an associated radius $r_{p} > 0$ . The transmission graph $G$ for $P$ is the directed graph w…

cs.CG2019

Reachability Oracles for Directed Transmission Graphs

Haim Kaplan, Wolfgang Mulzer, Liam Roditty +1

Let $P \subset 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 d…

cs.CG2017

Routing in Unit Disk Graphs

Haim Kaplan, Wolfgang Mulzer, Liam Roditty +1

Let $S \subset R^{2}$ be a set of $n$ sites. The unit disk graph $UD (S)$ on $S$ has vertex set $S$ and an edge between two distinct sites $s, t \in S$ if and only if $…

cs.DS2019

${- 1, 0, 1}$ -APSP and (min,max)-Product Problems

Hodaya Barr, Tsvi Kopelowitz, Ely Porat +1

In the ${- 1, 0, 1}$ -APSP problem the goal is to compute all-pairs shortest paths (APSP) on a directed graph whose edge weights are all from ${- 1, 0, 1}$ . In the (min,max)-product p…

cs.DS2017

An efficient strongly connected components algorithm in the fault tolerant model

Surender Baswana, Keerti Choudhary, Liam Roditty

In this paper we study the problem of maintaining the strongly connected components of a graph in the presence of failures. In particular, we show that given a directed graph $G=(V…

cs.DS2026

Weighted Emulators with Local Heaviest Edges Stretch for Undirected Graphs

Liam Roditty, Ariel Sapir

We introduce a generalized family of $\left( 2\cdot \left\lfloor \frac{k}{2} \right\rfloor-1, 2\cdot \left\lceil \frac{k}{2} \right\rceil \cdot W_{1} +\max\left\{0,2\cdot\left(\lef…

cs.DS2025

New approximate distance oracles and their applications

Avi Kadria, Liam Roditty

Let $G = (V, E)$ be an undirected graph with $n$ vertices and $m$ edges, and let $I^¼ = m / n$ . A \emph{distance oracle} is a data structure designed to answer approximate distance que…

cs.GT2024

The Complexity of Manipulation of k-Coalitional Games on Graphs

Hodaya Barr, Yohai Trabelsi, Sarit Kraus +2

In many settings, there is an organizer who would like to divide a set of agents into $k$ coalitions, and cares about the friendships within each coalition. Specifically, the organ…

cs.CG2024

Dynamic Connectivity in Disk Graphs

Alexander Baumann, Haim Kaplan, Katharina Klost +4

Let $S$ be a set of $n$ sites in the plane, so that every site $s \in S$ has an associated radius $r_{s} > 0$ . Let $D (S)$ be the disk intersection graph defined by $S$ , i.e…

cs.DS2026

Additive, Near-Additive, and Multiplicative Approximations for APSP in Weighted Undirected Graphs: Trade-offs and Algorithms

Liam Roditty, Ariel Sapir

We present a $+ 2 \sum_{i = 1}^{k + 1} W_{i}$ -APASP algorithm for dense weighted graphs with runtime $O ~ (n^{2 + \frac{1}{3 k + 2}})$ , where $W_{i}$ is the weight of an $i^{th}…

cs.CG2023

Insertion-Only Dynamic Connectivity in General Disk Graphs

Haim Kaplan, Katharina Klost, Kristin Knorr +2

Let $S \subseteq R^{2}$ be a set of $n$ \emph{sites} in the plane, so that every site $s \in S$ has an \emph{associated radius} $r_{s} > 0$ . Let $D (S)$ be the \emph{disk inter…

cs.DS2026

Improved Approximation Algorithms for n-Pairs Shortest Paths

Avi Kadria, Liam Roditty, Virginia Vassilevska Williams

Let $G = (V, E)$ be a graph with $n = ∣ V ∣$ nodes and $m = ∣ E ∣$ edges. The $t$ -Pairs Shortest Paths problem, introduced by Cohen [FOCS'93; SICOMP'99], asks to approximate the distan…

cs.DS2019

Algorithms and Hardness for Diameter in Dynamic Graphs

Bertie Ancona, Monika Henzinger, Liam Roditty +2

The diameter, radius and eccentricities are natural graph parameters. While these problems have been studied extensively, there are no known dynamic algorithms for them beyond the…

cs.DS2025

Improved girth approximation in weighted undirected graphs

Avi Kadria, Liam Roditty, Aaron Sidford +2

Let $G = (V, E, ℓ)$ be a $n$ -node $m$ -edge weighted undirected graph, where $ℓ : E \to (0, \infty)$ is a real \emph{length} function defined on its edges, and let $g$ den…

cs.DS2013

A Labeling Approach to Incremental Cycle Detection

Edith Cohen, Amos Fiat, Haim Kaplan +1

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 th…

cs.DS2010

Fast, precise and dynamic distance queries

Yair Bartal, Lee-Ad Gottlieb, Tsvi Kopelowitz +2

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 (uni…

cs.CG2019

Triangles and Girth in Disk Graphs and Transmission Graphs

Haim Kaplan, Katharina Klost, Wolfgang Mulzer +3

Let $S \subset R^{2}$ be a set of $n$ sites, where each $s \in S$ has an associated radius $r_{s} > 0$ . The disk graph $D (S)$ is the undirected graph with vertex set $S$ and a…

cs.CG2020

Dynamic Planar Voronoi Diagrams for General Distance Functions and their Algorithmic Applications

Haim Kaplan, Wolfgang Mulzer, Liam Roditty +2

We describe a new data structure for dynamic nearest neighbor queries in the plane with respect to a general family of distance functions. These include $L_{p}$ -norms and additively…

cs.DS2026

Faster Algorithms for $(2 k - 1)$ -Stretch Distance Oracles

Avi Kadria, Liam Roditty

Let $G = (V, E)$ be an undirected $n$ -vertices $m$ -edges graph with non-negative edge weights. In this paper, we present three new algorithms for constructing a $(2 k - 1)$ -stretch dist…

cs.DS2026

New Diameter Approximations via Distance Oracle Techniques

Yael Kirkpatrick, Liam Roditty, Richard Qi +1

Computing the diameter of a graph is a problem of great interest both in general algorithms research and specifically within fine-grained complexity, where it is a cornerstone hard…

Publications (34)

Stabbing Pairwise Intersecting Disks by Five Points

Compact routing schemes in undirected and directed graphs

On the Space Usage of Approximate Distance Oracles with Sub-2 Stretch

Relaxed spanners for directed disk graphs

Approximating the diameter of a graph

New routing techniques and their applications

Finding the Minimum-Weight k-Path

Towards Tight Approximation Bounds for Graph Diameter and Eccentricities

Approximating Cycles in Directed Graphs: Fast Algorithms for Girth and Roundtrip Spanners

SINR Diagrams: Towards Algorithmically Usable SINR Models of Wireless Networks

New algorithms for girth and cycle detection

Minimum Weight Cycles and Triangles: Equivalences and Algorithms

Tighter bounds for weighted and unweighted shortest cycle approximation

Dynamic Connectivity: Connecting to Networks and Geometry

Spanners for Directed Transmission Graphs

Reachability Oracles for Directed Transmission Graphs

Routing in Unit Disk Graphs

{−1,0,1}-APSP and (min,max)-Product Problems

An efficient strongly connected components algorithm in the fault tolerant model

Weighted Emulators with Local Heaviest Edges Stretch for Undirected Graphs

New approximate distance oracles and their applications

The Complexity of Manipulation of k-Coalitional Games on Graphs

Dynamic Connectivity in Disk Graphs

Additive, Near-Additive, and Multiplicative Approximations for APSP in Weighted Undirected Graphs: Trade-offs and Algorithms

Insertion-Only Dynamic Connectivity in General Disk Graphs

Improved Approximation Algorithms for n-Pairs Shortest Paths

Algorithms and Hardness for Diameter in Dynamic Graphs

Improved girth approximation in weighted undirected graphs

A Labeling Approach to Incremental Cycle Detection

Fast, precise and dynamic distance queries

Triangles and Girth in Disk Graphs and Transmission Graphs

Dynamic Planar Voronoi Diagrams for General Distance Functions and their Algorithmic Applications

Faster Algorithms for (2k−1)-Stretch Distance Oracles

New Diameter Approximations via Distance Oracle Techniques

${- 1, 0, 1}$ -APSP and (min,max)-Product Problems

Faster Algorithms for $(2 k - 1)$ -Stretch Distance Oracles