Algorithms for graph partitioning on the planted partition model

DOI10.1007/978-3-540-48413-4_23MaRDI QIDQ4941836zbMATH OpenFDO

Authors Anne Condon, Richard Karp

Publication date 19 July 2000

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-540-48413-4_23

zbMATH Keywords

algorithmbisection problempartitionprobability

Mathematics Subject Classification ID

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

Recommendations

• Algorithms for graph partitioning on the planted partition model
• Max Cut for Random Graphs with a Planted Partition
• The minimum bisection in the planted bisection model
• A Simple Message Passing Algorithm for Graph Partitioning Problems
• The minimum bisection in the planted bisection model

Cited in

(28)

• The Metropolis algorithm for graph bisection
• Exploring community structure in networks by consensus dynamics
• A note on probably certifiably correct algorithms
• Red light green light method for solving large Markov chains
• Algorithms for graph partitioning on the planted partition model
• Hill-climbing finds random planted bisections
• A spectral heuristic for bisecting random graphs
• Poisson approximation of subgraph counts in stochastic block models and a graphon model
• Finding Planted Partitions in Random Graphs with General Degree Distributions
• Belief propagation for graph partitioning
• scientific article; zbMATH DE number 1303593 (Why is no real title available?)
• Graph partitioning using learning automata
• Community detection and stochastic block models: recent developments
• Max Cut for Random Graphs with a Planted Partition
• scientific article; zbMATH DE number 1833396 (Why is no real title available?)
• Cut Size Statistics of Graph Bisection Heuristics
• On using learning automata for fast graph partitioning
• Parameterized Algorithms for Partitioning Graphs into Highly Connected Clusters
• New abilities and limitations of spectral graph bisection
• Compound Poisson approximation of subgraph counts in stochastic block models with multiple edges
• The minimum bisection in the planted bisection model
• The minimum bisection in the planted bisection model
• Approximation algorithms for semi-random partitioning problems
• A Simple Message Passing Algorithm for Graph Partitioning Problems
• Fundamentals of Computation Theory
• Spectral clustering and the high-dimensional stochastic blockmodel
• A note on edge-based graph partitioning and its linear algebraic structure
• Soft happy colourings and community structure of networks

This page was built for publication: Algorithms for graph partitioning on the planted partition model

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