Max Cut for Random Graphs with a Planted Partition

DOI10.1017/S0963548304006303MaRDI QIDQ4670352zbMATH OpenFDO

Authors Béla Bollobás, Alex Scott

Publication date 18 April 2005

Published in Combinatorics, Probability and Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1017/S0963548304006303

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• A simple spectral algorithm for recovering planted partitions
• Algorithms for graph partitioning on the planted partition model
• scientific article; zbMATH DE number 1418276
• General paritioning on random graphs
• Finding Planted Partitions in Random Graphs with General Degree Distributions

Cited in

(13)

• Cross-entropy and rare events for maximal cut and partition problems
• New abilities and limitations of spectral graph bisection
• Graph partitioning via adaptive spectral techniques
• Comparing recent methods in graph partitioning
• Finding Planted Partitions in Random Graphs with General Degree Distributions
• Clustering heterogeneous financial networks
• A simple spectral algorithm for recovering planted partitions
• scientific article; zbMATH DE number 1418276 (Why is no real title available?)
• Sparse graphs: metrics and random models
• Algorithms for graph partitioning on the planted partition model
• Improved algorithms for the random cluster graph model
• Semi-random Graphs with Planted Sparse Vertex Cuts: Algorithms for Exact and Approximate Recovery
• A Simple Message Passing Algorithm for Graph Partitioning Problems

This page was built for publication: Max Cut for Random Graphs with a Planted Partition

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