Bisecting sparse random graphs

DOI10.1002/1098-2418(200101)18:1%3C31::AID-RSA3%3E3.0.CO;2-1MaRDI QIDQ4761356zbMATH OpenOpenAlexFDO

Authors Malwina Luczak, Colin McDiarmid

Publication date 11 February 2001

Full work available at URL https://doi.org/10.1002/1098-2418(200101)18:1%3C31::aid-rsa3%3E3.0.co;2-1

zbMATH Keywords

bisection widthpartitionsprobabilitysparse random graphs

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Random graphs (graph-theoretic aspects) (05C80)

Recommendations

• A spectral heuristic for bisecting random graphs
• A spectral heuristic for bisecting random graphs
• Convergence of maximum bisection ratio of sparse random graphs
• The peculiar phase structure of random graph bisection
• Bipartite decomposition of random graphs
• Friendly bisections of random graphs
• Dismantling Sparse Random Graphs
• scientific article; zbMATH DE number 2019629
• Random Subgraphs in Sparse Graphs

Cites work

• Probabilistic methods for algorithmic discrete mathematics

Cited in

(18)

• The symmetry in the martingale inequality
• Clique percolation
• A spectral heuristic for bisecting random graphs
• The peculiar phase structure of random graph bisection
• scientific article; zbMATH DE number 4053679 (Why is no real title available?)
• scientific article; zbMATH DE number 125467 (Why is no real title available?)
• Crossing numbers of random graphs
• Modularity of Erdős-Rényi random graphs
• Modularity of Erdős-Rényi random graphs
• Bipartitioning of directed and mixed random graphs
• Sparse graphs: metrics and random models
• The minimum bisection in the planted bisection model
• The minimum bisection in the planted bisection model
• The cut metric, random graphs, and branching processes
• Friendly bisections of random graphs
• On the minimum bisection of random 3-regular graphs
• On perfectly friendly bisections of random graphs
• Cuts, cats, and complete graphs

This page was built for publication: Bisecting sparse random graphs

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