Partitioning graphs into balanced components

zbMATH Open1411.68085MaRDI QIDQ4633907FDOQ4633907

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

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

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)

Cited In (17)

• Partitioning a graph into small pieces with applications to path transversal
• Minimum nonuniform graph partitioning with unrelated weights
• Balanced connected graph partition
• Balanced graph partitioning
• Multiply balanced \(k\)-partitioning
• Approximation algorithms for the weighted \(t\)-uniform sparsest cut and some other graph partitioning problems
• Algorithms for the Balanced Edge Partitioning Problem
• An exact algorithm for min-max hyperstructure equipartition with a connected constraint
• 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
• Approximation algorithm for sparsest \(k\)-partitioning
• 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)