On computing discretized Ricci curvatures of graphs: local algorithms and (localized) fine-grained reductions
From MaRDI portal
Publication:6076351
DOI10.1016/j.tcs.2023.114127arXiv2208.09535OpenAlexW4385988600MaRDI QIDQ6076351
No author found.
Publication date: 21 September 2023
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/2208.09535
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Sublinear time algorithms for earth mover's distance
- Approximating the minimum vertex cover in sublinear time and a connection to distributed algorithms
- Ricci curvature of Markov chains on metric spaces
- Expanders are not hyperbolic
- Bochner's method for cell complexes and combinatorial Ricci curvature
- A Riemannian interpolation inequality à la Borell, Brascamp and Lieb
- Systematic evaluation of a new combinatorial curvature for complex networks
- Effect of Gromov-hyperbolicity parameter on cuts and expansions in graphs and some algorithmic implications
- Combinatorial Ricci flows on surfaces.
- Why did the shape of your network change? (On detecting network anomalies via non-local curvatures)
- Computing the Gromov hyperbolicity of a discrete metric space
- Prékopa-Leindler type inequalities on Riemannian manifolds, Jacobi fields, and optimal transport
- Ricci curvature of metric spaces
- Fast approximation and exact computation of negative curvature parameters of graphs
- Sketching Earth-Mover Distance on Graph Metrics
- Towards polynomial lower bounds for dynamic problems
- Euclidean versus Hyperbolic Congestion in Idealized versus Experimental Networks
- Improved Constant-Time Approximation Algorithms for Maximum Matchings and Other Optimization Problems
- Fast context-free grammar parsing requires fast boolean matrix multiplication
- Forman curvature for complex networks
- Diameters, centers, and approximating trees of delta-hyperbolicgeodesic spaces and graphs
- A Panoramic View of Riemannian Geometry
- The Brunn-Minkowski inequality
- On Choosing and Bounding Probability Metrics
- A Curved Brunn--Minkowski Inequality on the Discrete Hypercube, Or: What Is the Ricci Curvature of the Discrete Hypercube?
- ON SOME FINE-GRAINED QUESTIONS IN ALGORITHMS AND COMPLEXITY
- Probability Inequalities for Sums of Bounded Random Variables
- Subcubic Equivalences Between Graph Centrality Problems, APSP and Diameter
