207 research outputs found
Path-Reporting Distance Oracles with Logarithmic Stretch and Linear Size
No full textGiven an undirected graph G = (V, E, ) on n vertices with positive edge weights, a distance oracle is a space-efficient data structure that answers pairwise distance queries in fast runtime. The quality of a distance oracle is measured by three parameters: space, query time, and stretch. In a landmark paper by [Thorup and Zwick, 2001], they showed that for any integer parameter k ≥ 1, there exists a distance oracle with size O(kn^{1+1/k}), O(k) query time, and (2k-1)-stretch error on the approximate distances. After that, there has been a line of subsequent improvements which culminated in the optimal trade-off of O(n^{1+1/k}) space, O(1) query time, and (2k-1)-stretch [Chechik, 2015].
However, these line of constructions did not require that the distance oracle is capable of printing an actual path besides an approximate distance estimate, and there has been a performance gap between path-reporting distance oracles and ones that are not path-reporting. It is known that the earliest construction by [Thorup and Zwick, 2001] is path-reporting, but the parameters are worse by a factor of k. In a later construction by [Wulff-Nilsen, 2013], the query time was improved from O(k) to O(log k). Better trade-offs were discovered in [Elkin and Pettie, 2015] where the authors broke the O(kn^{1+1/k}) space barrier and achieved O(n^{1+1/k}log k) space with O(log k) query time, but their stretch was blown up to a polynomial O(k^{log_{4/3}7}); they also gave an alternative choice of O(n^{1+1/k}) space which is optimal, and O(k)-stretch which is also optimal up to a constant factor, but their query time rose exponentially to O(n^ε). In a recent work [Elkin and Shabat, 2023], the authors obtained significant improvements of O(n^{1+1/k}log k) space, O(k)-stretch, and O(log log k) query time, or O(n^{1+1/k}) space, O(klog k)-stretch, and O(log log k) query time.
All the above constructions of path-reporting distance oracles share a common barrier; that is, they could not achieve optimal space O(n^{1+1/k}) and stretch O(k) simultaneously within logarithmic query time; for example, in the natural regime where k = ⌈log n⌉, previous distance oracles had to pay an extra factor of log log n either in the space or stretch. As our result, we bypass this barrier by a new construction of path-reporting distance oracles with O(n^{1+1/k}) space and O(k)-stretch and O(log log k) query time
Magnetic interactions in spin-labeled Au nanoparticles
No full text© 2014 American Chemical Society. A series of gold nanoparticles functionalized with TEMPO-modified disulfide 2 have been prepared and studied by electron paramagnetic resonance (EPR) spectroscopy, UV-vis, transmission electron microscopy (TEM), energy dispersive X-ray analysis (EDX), and thermogravimetric analysis (TGA). In order to increase the packing of spin labels on the particle surface, heat-induced size evolution and ligand exchange reactions were used. The optimized synthesis included a one-pot reaction at room temperature that led to gold nanoparticles with a controlled large size (ca. 7 nm) and high coverage of radicals. These nanoparticles showed a |Δms| = 2 transition at half-field, which gives direct evidence of the presence of a high-spin state and permits an EPR study of the nature of the magnetic coupling between the spins. The results showed dominant antiferromagnetic interactions between radicals, but at lower temperatures, a ferromagnetic contribution was observed.This work was supported by the University of York Research Visitor Scheme, the DGI grant CONSOLIDERC (CTQ2006-06333), CSIC-PIF RAPCAM (PIF-08-017-3), AGAUR (2009-SGR-00516), and DGI grant POMAs (CTQ2010-19501). CIBER-BBN is an initiative funded by the VI National R&D&i Plan 2008-2011, Iniciativa Ingenio 2010, Consolider Program, CIBER Actions, and financed by the Instituto de Salud Carlos III with assistance from the European Regional Development Fund.Peer Reviewe
Faster Algorithms for Dual-Failure Replacement Paths
No full textGiven a simple weighted directed graph G = (V, E, ω) on n vertices as well as two designated terminals s, t ∈ V, our goal is to compute the shortest path from s to t avoiding any pair of presumably failed edges f₁, f₂ ∈ E, which is a natural generalization of the classical replacement path problem which considers single edge failures only.
This dual failure replacement paths problem was recently studied by Vassilevska Williams, Woldeghebriel and Xu [FOCS 2022] who designed a cubic time algorithm for general weighted digraphs which is conditionally optimal; in the same paper, for unweighted graphs where ω ≡ 1, the authors presented an algebraic algorithm with runtime Õ(n^{2.9146}), as well as a conditional lower bound of n^{8/3-o(1)} against combinatorial algorithms. However, it was unknown in their work whether fast matrix multiplication is necessary for a subcubic runtime in unweighted digraphs.
As our primary result, we present the first truly subcubic combinatorial algorithm for dual failure replacement paths in unweighted digraphs. Our runtime is Õ(n^{3-1/18}). Besides, we also study algebraic algorithms for digraphs with small integer edge weights from {-M, -M+1, ⋯, M-1, M}. As our secondary result, we obtained a runtime of Õ(Mn^{2.8716}), which is faster than the previous bound of Õ(M^{2/3}n^{2.9144} + Mn^{2.8716}) from [Vassilevska Williams, Woldeghebriela and Xu, 2022]
Near Optimal Algorithm for the Directed Single Source Replacement Paths Problem
No full textIn the Single Source Replacement Paths (SSRP) problem we are given a graph G = (V, E), and a shortest paths tree K̂ rooted at a node s, and the goal is to output for every node t ∈ V and for every edge e in K̂ the length of the shortest path from s to t avoiding e.
We present an Õ(m√n + n²) time randomized combinatorial algorithm for unweighted directed graphs. Previously such a bound was known in the directed case only for the seemingly easier problem of replacement path where both the source and the target nodes are fixed.
Our new upper bound for this problem matches the existing conditional combinatorial lower bounds. Hence, (assuming these conditional lower bounds) our result is essentially optimal and completes the picture of the SSRP problem in the combinatorial setting.
Our algorithm naturally extends to the case of small, rational edge weights. In the full version of the paper, we strengthen the existing conditional lower bounds in this case by showing that any O(mn^(1/2-ε)) time (combinatorial or algebraic) algorithm for some fixed ε > 0 yields a truly sub-cubic algorithm for the weighted All Pairs Shortest Paths problem (previously such a bound was known only for the combinatorial setting)
Average Distance Queries through Weighted Samples in Graphs and Metric Spaces: High Scalability with Tight Statistical Guarantees
No full textThe average distance from a node to all other nodes in a graph, or from a query point in a metric space to a set of points, is a fundamental quantity in data analysis. The inverse of the average distance, known as the (classic) closeness centrality of a node, is a popular importance measure in the study of social networks. We develop novel structural insights on the sparsifiability of the distance relation via weighted sampling. Based on that, we present highly practical algorithms with strong statistical guarantees for fundamental problems. We show that the average distance (and hence the centrality) for all nodes in a graph can be estimated using O(epsilon^{-2}) single-source distance computations. For a set V of n points in a metric space, we show that after preprocessing which uses O(n) distance computations we can compute a weighted sample S subset of V of size O(epsilon^{-2}) such that the average distance from any query point v to V can be estimated from the distances from v to S. Finally, we show that for a set of points V in a metric space, we can estimate the average pairwise distance using O(n+epsilon^{-2}) distance computations. The estimate is based on a weighted sample of O(epsilon^{-2}) pairs of points, which is computed using O(n) distance computations. Our estimates are unbiased with normalized mean square error (NRMSE) of at most epsilon. Increasing the sample size by a O(log(n)) factor ensures that the probability that the relative error exceeds epsilon is polynomially small
Deterministic Combinatorial Replacement Paths and Distance Sensitivity Oracles
No full textIn this work we derandomize two central results in graph algorithms, replacement paths and distance sensitivity oracles (DSOs) matching in both cases the running time of the randomized algorithms.
For the replacement paths problem, let G = (V,E) be a directed unweighted graph with n vertices and m edges and let P be a shortest path from s to t in G. The replacement paths problem is to find for every edge e in P the shortest path from s to t avoiding e. Roditty and Zwick [ICALP 2005] obtained a randomized algorithm with running time of O~(m sqrt{n}). Here we provide the first deterministic algorithm for this problem, with the same O~(m sqrt{n}) time. Due to matching conditional lower bounds of Williams et al. [FOCS 2010], our deterministic combinatorial algorithm for the replacement paths problem is optimal up to polylogarithmic factors (unless the long standing bound of O~(mn) for the combinatorial boolean matrix multiplication can be improved). This also implies a deterministic algorithm for the second simple shortest path problem in O~(m sqrt{n}) time, and a deterministic algorithm for the k-simple shortest paths problem in O~(k m sqrt{n}) time (for any integer constant k > 0).
For the problem of distance sensitivity oracles, let G = (V,E) be a directed graph with real-edge weights. An f-Sensitivity Distance Oracle (f-DSO) gets as input the graph G=(V,E) and a parameter f, preprocesses it into a data-structure, such that given a query (s,t,F) with s,t in V and F subseteq E cup V, |F| <=f being a set of at most f edges or vertices (failures), the query algorithm efficiently computes the distance from s to t in the graph G \ F (i.e., the distance from s to t in the graph G after removing from it the failing edges and vertices F).
For weighted graphs with real edge weights, Weimann and Yuster [FOCS 2010] presented several randomized f-DSOs. In particular, they presented a combinatorial f-DSO with O~(mn^{4-alpha}) preprocessing time and subquadratic O~(n^{2-2(1-alpha)/f}) query time, giving a tradeoff between preprocessing and query time for every value of 0 < alpha < 1. We derandomize this result and present a combinatorial deterministic f-DSO with the same asymptotic preprocessing and query time
EPR investigations of organic non-covalent assemblies with spin labels and spin probes
No full textThe object of the present report is to review the articles appeared in the literature in the last few years describing the use of EPR spectroscopy to investigate the properties of purely organic non-covalent assemblies in liquid solution with spin labels and spin probes
Faster algorithms for computing maximal 2-connected subgraphs in sparse directed graphs
No full textConnectivity related concepts are of fundamental interest in graph theory. The area has received extensive attention over four decades, but many problems remain unsolved, especially for directed graphs. A directed graph is 2-edge-connected (resp., 2-vertex-connected) if the removal of any edge (resp., vertex) leaves the graph strongly connected. In this paper we present improved algorithms for computing the maximal 2-edge and 2- vertex-connected subgraphs of a given directed graph. These problems were first studied more than 35 years ago, with eO(mn) time algorithms for graphs with m edges and n vertices being known since the late 1980s. In contrast, the same problems for undirected graphs are known to be solvable in linear time. Henzinger et al. [ICALP 2015] recently introduced O(n2) time algo- rithms for the directed case, thus improving the running times for dense graphs. Our new algorithms run in time O(m3=2), which further improves the running times for sparse graphs. The notion of 2-connectivity naturally generalizes to k-connectivity for k > 2. For constant values of k, we extend one of our algorithms to compute the maximal k-edge-connected in time O(m3=2 log n), improving again for sparse graphs the best known algorithm by Henzinger et al. [ICALP 2015] that runs in O(n2 log n) time
Fully Dynamic All-Pairs Shortest Paths: Breaking the O(n) Barrier
No full textA fully dynamic approximate distance oracle is a distance reporting data structure that supports dynamic insert edge and delete edge operations. In this paper we break a longstanding barrier in the design of fully dynamic all-pairs approximate distance oracles.
All previous results for this model incurred an amortized cost of at least Omega(n) per operation. We present the first construction that provides constant stretch and o(m) amortized update time. For graphs that are not too dense (where |E| = O(|V|^{2-delta}) for some delta>0 we break the O(n) barrier and provide the first construction with constant stretch and o(n) amortized cost
- …
