Local algorithms, regular graphs of large girth, and random regular graphs

DOI10.1007/s00493-016-3236-xzbMath1438.05137arXiv1308.0266OpenAlexW2964041705MaRDI QIDQ1715061

Carlos Hoppen, Nicholas C. Wormald

Publication date: 1 February 2019

Published in: Combinatorica (Search for Journal in Brave)

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

zbMATH Keywords

regular graphslarge girth

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Random graphs (graph-theoretic aspects) (05C80) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items (11)

Total domination in regular graphs ⋮ Asymptotic bounds on total domination in regular graphs ⋮ A branch‐and‐cut algorithm for a bipartite graph construction problem in digital communication systems ⋮ Suboptimality of local algorithms for a class of max-cut problems ⋮ Improved replica bounds for the independence ratio of random regular graphs ⋮ Correlation Bounds for Distant Parts of Factor of IID Processes ⋮ Mutual information decay for factors of i.i.d. ⋮ Entropy inequalities for factors of IID ⋮ Minimum 2-dominating sets in regular graphs ⋮ Fractional Chromatic Number, Maximum Degree, and Girth ⋮ The matching process and independent process in random regular graphs and hypergraphs

This page was built for publication: Local algorithms, regular graphs of large girth, and random regular graphs