Effect of Gromov-hyperbolicity parameter on cuts and expansions in graphs and some algorithmic implications

DOI10.1007/s00453-017-0291-7zbMath1391.68049arXiv1510.08779OpenAlexW3106522097MaRDI QIDQ1709598

Bhaskar Das Gupta, Nasim Mobasheri, Farzane Yahyanejad, Marek Karpinski

Publication date: 6 April 2018

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1510.08779

zbMATH Keywords

approximation algorithmsGromov hyperbolicityminimum cutsnode expansion

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Analysis of algorithms (68W40) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)

Related Items (5)

Fast approximation and exact computation of negative curvature parameters of graphs ⋮ Why did the shape of your network change? (On detecting network anomalies via non-local curvatures) ⋮ On computing discretized Ricci curvatures of graphs: local algorithms and (localized) fine-grained reductions ⋮ A review of two network curvature measures ⋮ Fast Approximation and Exact Computation of Negative Curvature Parameters of Graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Finding paths with minimum shared edges
• The minimum vulnerability problem
• On set expansion problems and the small set expansion conjecture
• Graph minors. I. Excluding a forest
• Expanders are not hyperbolic
• Scaled Gromov four-point condition for network graph curvature computation
• Computing the Gromov hyperbolicity of a discrete metric space
• Additive spanners and distance and routing labeling schemes for hyperbolic graphs
• Approximations for the isoperimetric and spectral profile of graphs and related parameters
• Graph expansion and the unique games conjecture
• Euclidean versus Hyperbolic Congestion in Idealized versus Experimental Networks
• On network design problems: fixed cost flows and the covering steiner problem
• Geodesics and almost geodesic cycles in random regular graphs
• Subexponential Algorithms for Unique Games and Related Problems
• Diameters, centers, and approximating trees of delta-hyperbolicgeodesic spaces and graphs
• Packing and Covering δ-Hyperbolic Spaces by Balls
• Finite Transitive Graph Embeddings into a Hyperbolic Metric Space Must Stretch or Squeeze
• Lack of Hyperbolicity in Asymptotic Erdös–Renyi Sparse Random Graphs
• Succinct Greedy Geometric Routing Using Hyperbolic Geometry
• Scaled Gromov hyperbolic graphs
• Min-max Graph Partitioning and Small Set Expansion
• Algorithms and Computation

This page was built for publication: Effect of Gromov-hyperbolicity parameter on cuts and expansions in graphs and some algorithmic implications