
Universität Bonn > Institut für Informatik > Abteilung V  
CSReports 2016  Copyright 2016 Universität Bonn, Institut für Informatik, Abt. V  
85361 23.02.2016 
Effect of GromovHyperbolicity Parameters on Cuts and Expansions in Graphs and Some Algorithmic Implications
Bhaskar DasGupta, Marek Karpinski, Nasim Mobasheri, Farzaneh Yahyanejad [Download PostScript] [Download PDF]
δhyperbolic graphs, originally conceived by Gromov in 1987, include nontrivial interesting classes of “nonexpander” graphs; for fixed δ, such graphs are simply called hyperbolic graphs. Our goal in this paper is to study the effect of the hyperbolicity measure δ on expansion and cutsize bounds on graphs (here δ need not be a constant, i.e., the graph is not necessarily hyperbolic), and investigate up to what values of δ these results could provide improved approximation algorithms for related combinatorial problems. To this effect, we provide the following results.


Last Change:
02/23/16 at 10:27:52
English 
Universität Bonn > Institut für Informatik > Abteilung V 