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

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

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

(18)

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

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)