Solving vertex cover in polynomial time on hyperbolic random graphs

DOI10.1007/s00224-021-10062-9OpenAlexW3209460892WikidataQ115608874 ScholiaQ115608874MaRDI QIDQ2701066

Tobias Friedrich, Thomas Bläsius, Philipp Fischbeck, Maximilian Katzmann

Publication date: 27 April 2023

Published in: Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00224-021-10062-9

zbMATH Keywords

random graphshyperbolic geometryvertex coverefficient algorithm

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx) Theory of computing (68Qxx) Graph theory (05Cxx)

Related Items (2)

The impact of heterogeneity and geometry on the proof complexity of random satisfiability ⋮ A probabilistic algorithm for vertex cover

Uses Software

• Pajek
• Pajek datasets
• SNAP
• KONECT
• GitHub

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Improved upper bounds for vertex cover
• Branch-and-reduce exponential/FPT algorithms in practice: a case study of vertex cover
• Introduction to hyperbolic geometry
• On the existence of subexponential parameterized algorithms
• Exact algorithms for maximum independent set
• Statistical mechanics of complex networks
• Random Hyperbolic Graphs: Degree Sequence and Clustering
• A measure & conquer approach for the analysis of exact algorithms
• Lectures on Complex Networks
• On the Diameter of Hyperbolic Random Graphs
• Hyperbolic Random Graphs: Separators and Treewidth
• A Bound for the Diameter of Random Hyperbolic Graphs
• Parameterized Algorithms
• Concentration of Measure for the Analysis of Randomized Algorithms

This page was built for publication: Solving vertex cover in polynomial time on hyperbolic random graphs