A Polylogarithmic Approximation of the Minimum Bisection
From MaRDI portal
Publication:2784494
DOI10.1137/S0097539701387660zbMath1015.68240MaRDI QIDQ2784494
Robert Krauthgamer, Uriel Feige
Publication date: 23 April 2002
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/s0097539701387660
dynamic programming; graph partitioning; approximation algorithms; divide and conquer; graph separators
Related Items
Minimum Bisection Is Fixed-Parameter Tractable, Unnamed Item, Unnamed Item, Unnamed Item, Dynamic Balanced Graph Partitioning, Optimizing streaming graph partitioning via a heuristic greedy method and caching strategy, On the minimum bisection of random 3-regular graphs, 3D geo-graphs: efficient flip verification for the spherical zoning problem, Graph clustering, Techniques from combinatorial approximation algorithms yield efficient algorithms for random 2\(k\)-SAT, Solving the minimum bisection problem using a biologically inspired computational model, Upper bounds on the bisection width of 3- and 4-regular graphs, On the complexity of finding balanced oneway cuts, Balanced cut approximation in random geometric graphs, Distributed balanced partitioning via linear embedding, Impact of minimum-cut density-balanced partitioning solutions in distributed webpage ranking, Competitive clustering of stochastic communication patterns on a ring, Exact recovery in the Ising blockmodel, Linear kernels for separating a graph into components of bounded size, Inoculation strategies for victims of viruses and the sum-of-squares partition problem, Bisection of bounded treewidth graphs by convolutions, A semidefinite programming approach to the hypergraph minimum bisection problem
