Solving vertex cover in polynomial time on hyperbolic random graphs

DOI10.4230/LIPICS.STACS.2020.25MaRDI QIDQ5874296zbMATH OpenFDO

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

Publication date 7 February 2023

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

zbMATH Keywords

efficient algorithmhyperbolic geometryrandom graphsvertex cover

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Recommendations

• Solving vertex cover in polynomial time on hyperbolic random graphs
• Analytical and experimental comparison of six algorithms for the vertex cover problem
• Analysis and comparison of three algorithms for the vertex cover problem on large graphs with low memory capacities
• Greedy Local Search and Vertex Cover in Sparse Random Graphs
• On approximation of the vertex cover problem in hypergraphs

Cited in

(4)

• On the largest component of subcritical random hyperbolic graphs
• Solving vertex cover in polynomial time on hyperbolic random graphs
• A Randomized Polynomial Kernelization for Vertex Cover with a Smaller Parameter
• Separator theorem and algorithms for planar hyperbolic graphs

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

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