Zobrazeno 1 - 10
of 3 149
pro vyhledávání: '"Gutenberg A"'
Expander decompositions have become one of the central frameworks in the design of fast algorithms. For an undirected graph $G=(V,E)$, a near-optimal $\phi$-expander decomposition is a partition $V_1, V_2, \ldots, V_k$ of the vertex set $V$ where eac
Externí odkaz:
http://arxiv.org/abs/2410.13451
Autor:
Brand, Jan van den, Chen, Li, Kyng, Rasmus, Liu, Yang P., Meierhans, Simon, Gutenberg, Maximilian Probst, Sachdeva, Sushant
We give the first almost-linear total time algorithm for deciding if a flow of cost at most $F$ still exists in a directed graph, with edge costs and capacities, undergoing decremental updates, i.e., edge deletions, capacity decreases, and cost incre
Externí odkaz:
http://arxiv.org/abs/2407.10830
In this paper, we investigate the question of whether the electrical flow routing is a good oblivious routing scheme on an $m$-edge graph $G = (V, E)$ that is a $\Phi$-expander, i.e. where $\lvert \partial S \rvert \geq \Phi \cdot \mathrm{vol}(S)$ fo
Externí odkaz:
http://arxiv.org/abs/2406.07252
In this work, we present the first algorithm to compute expander decompositions in an $m$-edge directed graph with near-optimal time $\tilde{O}(m)$. Further, our algorithm can maintain such a decomposition in a dynamic graph and again obtains near-op
Externí odkaz:
http://arxiv.org/abs/2403.04542
We present a general toolbox, based on new vertex sparsifiers, for designing data structures to maintain shortest paths in dynamic graphs. In an $m$-edge graph undergoing edge insertions and deletions, our data structures give the first algorithms fo
Externí odkaz:
http://arxiv.org/abs/2311.06402
Autor:
Brand, Jan van den, Chen, Li, Kyng, Rasmus, Liu, Yang P., Peng, Richard, Gutenberg, Maximilian Probst, Sachdeva, Sushant, Sidford, Aaron
We provide an algorithm which, with high probability, maintains a $(1-\epsilon)$-approximate maximum flow on an undirected graph undergoing $m$-edge additions in amortized $m^{o(1)} \epsilon^{-3}$ time per update. To obtain this result, we provide a
Externí odkaz:
http://arxiv.org/abs/2311.03174
Autor:
Brand, Jan van den, Chen, Li, Kyng, Rasmus, Liu, Yang P., Peng, Richard, Gutenberg, Maximilian Probst, Sachdeva, Sushant, Sidford, Aaron
We give a deterministic $m^{1+o(1)}$ time algorithm that computes exact maximum flows and minimum-cost flows on directed graphs with $m$ edges and polynomially bounded integral demands, costs, and capacities. As a consequence, we obtain the first run
Externí odkaz:
http://arxiv.org/abs/2309.16629
Autor:
Al-Hamdo, Hassan, Wagner, Tobias, Lytvynenko, Yaryna, Kendzo, Gutenberg, Reimers, Sonka, Ruhwedel, Moritz, Yaqoob, Misbah, Vasyuchka, Vitaliy I., Pirro, Philipp, Sinova, Jairo, Kläui, Mathias, Jourdan, Martin, Gomonay, Olena, Weiler, Mathias
Publikováno v:
Phys. Rev. Lett. 131, 046701 (2023)
We investigate magnetization dynamics of Mn$_{2}$Au/Py (Ni$_{80}$Fe$_{20}$) thin film bilayers using broadband ferromagnetic resonance (FMR) and Brillouin light scattering spectroscopy. Our bilayers exhibit two resonant modes with zero-field frequenc
Externí odkaz:
http://arxiv.org/abs/2302.07915
We provide the first deterministic data structure that given a weighted undirected graph undergoing edge insertions, processes each update with polylogarithmic amortized update time and answers queries for the distance between any pair of vertices in
Externí odkaz:
http://arxiv.org/abs/2211.04217
We present a very simple and intuitive algorithm to find balanced sparse cuts in a graph via shortest-paths. Our algorithm combines a new multiplicative-weights framework for solving unit-weight multi-commodity flows with standard ball growing argume
Externí odkaz:
http://arxiv.org/abs/2209.08845