Beyond Good Shapes: Diffusion-Based Graph Partitioning Is Relaxed Cut Optimization

DOI10.1007/978-3-642-17514-5_33MaRDI QIDQ3060790zbMATH OpenOpenAlexFDO

Authors Henning Meyerhenke

Publication date 9 December 2010

Published in Algorithms and Computation (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-17514-5_33

zbMATH Keywords

diffusive graph partitioningdisturbed diffusionrelaxed cut optimization

Mathematics Subject Classification ID

Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Recommendations

• Beyond good partition shapes: an analysis of diffusive graph partitioning
• scientific article; zbMATH DE number 3991298
• Solving graph partitioning on sparse graphs: cuts, projections, and extended formulations
• Disturbed diffusive processes for solving partitioning problems on graphs
• On the Optimality of the Median Cut Spectral Bisection Graph Partitioning Method
• An efficient semidefinite programming relaxation for the graph partition problem
• Isoperimetric Partitioning: A New Algorithm for Graph Partitioning
• Semidefinite programming relaxations for the graph partitioning problem
• An improved rounding method and semidefinite programming relaxation for graph partition

Cited in

(2)

• Disturbed diffusive processes for solving partitioning problems on graphs
• Beyond good partition shapes: an analysis of diffusive graph partitioning

Describes a project that uses

Uses Software

• DibaP
• PT-Scotch
• FOS/C

This page was built for publication: Beyond Good Shapes: Diffusion-Based Graph Partitioning Is Relaxed Cut Optimization

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