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

DOI10.1007/s00453-017-0291-7zbMath1391.68049arXiv1510.08779MaRDI 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 algorithms; Gromov hyperbolicity; minimum cuts; node expansion

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

68W40: Analysis of algorithms

05C85: Graph algorithms (graph-theoretic aspects)

68W25: Approximation algorithms

Related Items

Fast Approximation and Exact Computation of Negative Curvature Parameters of Graphs, On computing discretized Ricci curvatures of graphs: local algorithms and (localized) fine-grained reductions, A review of two network curvature measures, Why did the shape of your network change? (On detecting network anomalies via non-local curvatures), 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