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)

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

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)