Partitioning graphs into balanced components

MaRDI QIDQ4633907zbMATH OpenFDO

Authors Robert Krauthgamer, Joseph (Seffi) Naor, Roy Schwartz

Publication date 6 May 2019

Full work available at URL https://dl.acm.org/citation.cfm?id=1496872

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25)

Recommendations

• Balanced graph partitioning
• Improved approximation algorithms for balanced partitioning problems
• Fast Approximate Graph Partitioning Algorithms
• Approximation algorithm for sparsest \(k\)-partitioning
• Balanced partitions of trees and applications

Cited in

(23)

• An exact algorithm for min-max hyperstructure equipartition with a connected constraint
• Partitioning a graph into small pieces with applications to path transversal
• Balanced partitions of trees and applications
• Balanced tree partition problems with virtual nodes
• Metaheuristics for the minimum gap graph partitioning problem
• Approximation algorithms for the weighted t-uniform sparsest cut and some other graph partitioning problems
• Fast balanced partitioning is hard even on grids and trees
• Fast Approximate Graph Partitioning Algorithms
• Improved approximation algorithms for balanced partitioning problems
• Minimum nonuniform graph partitioning with unrelated weights
• Approximation Algorithms for CSPs
• Dynamic balanced graph partitioning
• Non-uniform graph partitioning
• Approximation algorithm for sparsest \(k\)-partitioning
• Multiply balanced k-partitioning
• Algorithms for the Balanced Edge Partitioning Problem
• Balanced graph partitioning based on mixed 0-1 linear programming and iteration vertex relocation algorithm
• An exact algorithm for the minimum gap graph partitioning problem
• An improved approximation algorithm for dynamic minimum linear arrangement
• Efficient partitioning algorithms for optimizing big graph computation
• Improved bounds for online balanced graph re-partitioning
• Balanced connected graph partition
• Balanced graph partitioning

This page was built for publication: Partitioning graphs into balanced components

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