The solution of some random NP-hard problems in polynomial expected time
From MaRDI portal
Publication:3031922
DOI10.1016/0196-6774(89)90001-1zbMath0689.68049OpenAlexW2016776056WikidataQ56324140 ScholiaQ56324140MaRDI QIDQ3031922
Publication date: 1989
Published in: Journal of Algorithms (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0196-6774(89)90001-1
graph partitioningNP-completeaverage-case complexity3-PartitionGraph k- colourabilitySmall equitable cut
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Complexity of computation (including implicit computational complexity) (03D15)
Related Items
A new probabilistic analysis of Karger's randomized algorithm for minimum cut problems, On independent sets in random graphs, Expected complexity of graph partitioning problems, Unnamed Item, Probabilistic hyperedge replacement grammars, Random Instances of Problems in NP – Algorithms and Statistical Physics, A new unifying heuristic algorithm for the undirected minimum cut problems using minimum range cut algorithms, The Metropolis algorithm for graph bisection, Joint Community Detection and Rotational Synchronization via Semidefinite Programming, Refining the phase transition in combinatorial search, Find Your Place: Simple Distributed Algorithms for Community Detection, Combinatorial statistics and the sciences, Coloring k-colorable graphs in constant expected parallel time, Mutual information for the sparse stochastic block model, A Spectral Method for Joint Community Detection and Orthogonal Group Synchronization, Asymptotic uncertainty quantification for communities in sparse planted bi-section models, Learning sparse graphons and the generalized Kesten-Stigum threshold, Spectral Clustering via Adaptive Layer Aggregation for Multi-Layer Networks, Near-optimal dominating sets in dense random graphs in polynomial expected time, Asymptotic mutual information for the balanced binary stochastic block model, Step-by-step community detection in volume-regular graphs, Disentangling group and link persistence in dynamic stochastic block models, Reconstruction and estimation in the planted partition model, Graph Partitioning via Adaptive Spectral Techniques, Contiguity and non-reconstruction results for planted partition models: the dense case, Coloring random graphs, Community Detection and Stochastic Block Models, Complexity analysis of a decentralised graph colouring algorithm, Why almost all \(k\)-colorable graphs are easy to color, Community detection in sparse networks via Grothendieck's inequality, Unnamed Item, Consistent nonparametric estimation for heavy-tailed sparse graphs, Exact recovery in the Ising blockmodel, The replica symmetric phase of random constraint satisfaction problems, An expected polynomial time algorithm for coloring 2-colorable 3-graphs, Deciding \(k\)-colorability in expected polynomial time, Distributed community detection in dynamic graphs, Distributed Community Detection in Dynamic Graphs
