Hyperbolic random graphs: separators and treewidth

DOI10.4230/LIPICS.ESA.2016.15zbMATH Open1397.05162OpenAlexW2533979148MaRDI QIDQ4606284FDOQ4606284

Tobias Friedrich, Thomas Bläsius, Anton Krohmer

Publication date: 2 March 2018

Full work available at URL: http://dx.doi.org/10.4230/LIPIcs.ESA.2016.15

Recommendations

• On the diameter of hyperbolic random graphs
• On the hyperbolicity of small-world and treelike random graphs
• On computing the hyperbolicity of real-world graphs
• Cliques in hyperbolic random graphs
• On the hyperbolicity of small-world and treelike random graphs

zbMATH Keywords

treewidthseparatorspower-law graphsscale-free networkshyperbolic random graphs

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25)

Cited In (14)

• From Graph Theory to Network Science: The Natural Emergence of Hyperbolicity (Tutorial)
• The diameter of KPKVB random graphs
• On the largest component of subcritical random hyperbolic graphs
• First-Order Model-Checking in Random Graphs and Complex Networks
• Topology and geometry of random 2-dimensional hypertrees
• Sampling Geometric Inhomogeneous Random Graphs in Linear Time
• Title not available (Why is that?)
• Geometric inhomogeneous random graphs
• Cover and hitting times of hyperbolic random graphs
• On the treewidth of random geometric graphs and percolated grids
• On the Diameter of Hyperbolic Random Graphs
• Greedy routing and the algorithmic small-world phenomenon
• Solving vertex cover in polynomial time on hyperbolic random graphs
• On the hyperbolicity of small-world and treelike random graphs

This page was built for publication: Hyperbolic random graphs: separators and treewidth

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4606284)