Zobrazeno 1 - 10
of 1 253
pro vyhledávání: '"Bernstein, Aaron"'
We consider the foundational problem of maintaining a $(1-\varepsilon)$-approximate maximum weight matching (MWM) in an $n$-node dynamic graph undergoing edge insertions and deletions. We provide a general reduction that reduces the problem on graphs
Externí odkaz:
http://arxiv.org/abs/2410.18936
In the restricted shortest paths problem, we are given a graph $G$ whose edges are assigned two non-negative weights: lengths and delays, a source $s$, and a delay threshold $D$. The goal is to find, for each target $t$, the length of the shortest $(
Externí odkaz:
http://arxiv.org/abs/2410.17179
In the load-balancing problem, we have an $n$-vertex bipartite graph $G=(L, R, E)$ between a set of clients and servers. The goal is to find an assignment of all clients to the servers, while minimizing the maximum load on each server, where load of
Externí odkaz:
http://arxiv.org/abs/2410.16094
Given a weighted graph $G$, a $(\beta,\varepsilon)$-hopset $H$ is an edge set such that for any $s,t \in V(G)$, where $s$ can reach $t$ in $G$, there is a path from $s$ to $t$ in $G \cup H$ which uses at most $\beta$ hops whose length is in the range
Externí odkaz:
http://arxiv.org/abs/2407.10249
We present a combinatorial algorithm for computing exact maximum flows in directed graphs with $n$ vertices and edge capacities from $\{1,\dots,U\}$ in $n^{2+o(1)}\log U$ time, which is almost optimal in dense graphs. Our algorithm is a novel impleme
Externí odkaz:
http://arxiv.org/abs/2406.03648
The aspect ratio of a (positively) weighted graph $G$ is the ratio of its maximum edge weight to its minimum edge weight. Aspect ratio commonly arises as a complexity measure in graph algorithms, especially related to the computation of shortest path
Externí odkaz:
http://arxiv.org/abs/2308.13054
Autor:
Ashvinkumar, Vikrant, Bernstein, Aaron, Cao, Nairen, Grunau, Christoph, Haeupler, Bernhard, Jiang, Yonggang, Nanongkai, Danupon, Su, Hsin Hao
This paper presents parallel and distributed algorithms for single-source shortest paths when edges can have negative weights (negative-weight SSSP). We show a framework that reduces negative-weight SSSP in either setting to $n^{o(1)}$ calls to any S
Externí odkaz:
http://arxiv.org/abs/2303.00811
In the weighted load balancing problem, the input is an $n$-vertex bipartite graph between a set of clients and a set of servers, and each client comes with some nonnegative real weight. The output is an assignment that maps each client to one of its
Externí odkaz:
http://arxiv.org/abs/2301.07007
Autor:
Bernstein, Aaron, Wein, Nicole
For an n-vertex directed graph $G = (V,E)$, a $\beta$-\emph{shortcut set} $H$ is a set of additional edges $H \subseteq V \times V$ such that $G \cup H$ has the same transitive closure as $G$, and for every pair $u,v \in V$, there is a $uv$-path in $
Externí odkaz:
http://arxiv.org/abs/2207.04507