Max Cut for Random Graphs with a Planted Partition

DOI10.1017/S0963548304006303zbMATH Open1102.68089MaRDI QIDQ4670352FDOQ4670352

Authors: Béla Bollobás, Alex Scott 

Publication date: 18 April 2005

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

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

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)

Cited In (11)

• 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
• Title not available (Why is that?)
• Sparse graphs: metrics and random models
• Algorithms for graph partitioning on the planted partition model
• Improved algorithms for the random cluster graph model
• Title not available (Why is that?)
• 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)