A computational study of graph partitioning
From MaRDI portal
For a graph with weights on edges, the graph partitioning problem is the problem of partitioning the node set into \(k\) disjoint subsets of specified size so as to minimize the total weight of the edges connecting nodes in distinct subsets of the partition. This paper provides a numerical way on the use of an eigenvalue-based technique to find upper and lower bounds for the problem. Results for the case \(k= 2\) with up to thousand nodes are given, and for small graphs some results of the case \(k= 3\) are also presented.
Recommendations
- Algorithms for graph partitioning problems by means of eigenspace relaxations
- A projection technique for partitioning the nodes of a graph
- Spectral bounds for graph partitioning with prescribed partition sizes
- Constructive Heuristics and Lower Bounds for Graph Partitioning Based on a Principal-Components Approximation
Cites work
- \(\lambda_ 1\), isoperimetric inequalities for graphs, and superconcentrators
- A MIMD implementation of a parallel Euler solver for unstructured grids
- A New Heuristic for Partitioning the Nodes of a Graph
- A projection technique for partitioning the nodes of a graph
- A Version of the Bundle Idea for Minimizing a Nonsmooth Function: Conceptual Idea, Convergence Analysis, Numerical Results
- An Algorithm for Partitioning the Nodes of a Graph
- An Efficient Heuristic Procedure for Partitioning Graphs
- scientific article; zbMATH DE number 3912096 (Why is no real title available?)
- scientific article; zbMATH DE number 4076973 (Why is no real title available?)
- scientific article; zbMATH DE number 3717357 (Why is no real title available?)
- scientific article; zbMATH DE number 49142 (Why is no real title available?)
- scientific article; zbMATH DE number 3554030 (Why is no real title available?)
- Lower Bounds for the Partitioning of Graphs
- Matrix Analysis
- More bounds for eigenvalues using traces
- Optimal linear labelings and eigenvalues of graphs
- Optimization by Simulated Annealing: An Experimental Evaluation; Part I, Graph Partitioning
- The equipartition polytope. I: Formulations, dimension and basic facets
Cited in
(35)- Spectral partitioning with multiple eigenvectors
- An optimal tree search method for the manufacturing systems cell formation problem
- Spectra and optimal partitions of weighted graphs
- Spectral methods for graph bisection problems.
- Algorithms for graph partitioning problems by means of eigenspace relaxations
- On spectral bounds for the \(k\)-partitioning of graphs
- A projection technique for partitioning the nodes of a graph
- An exact algorithm for graph partitioning
- Semidefinite programming relaxations for the graph partitioning problem
- Spectral bounds for graph partitioning with prescribed partition sizes
- Semidefinite programming and eigenvalue bounds for the graph partition problem
- scientific article; zbMATH DE number 1617249 (Why is no real title available?)
- General introduction to graph partitioning
- Constructive Heuristics and Lower Bounds for Graph Partitioning Based on a Principal-Components Approximation
- Comparison of algorithms in graph partitioning
- scientific article; zbMATH DE number 6501141 (Why is no real title available?)
- scientific article; zbMATH DE number 3855167 (Why is no real title available?)
- scientific article; zbMATH DE number 3871421 (Why is no real title available?)
- A class of bounded approximation algorithms for graph partitioning
- scientific article; zbMATH DE number 5761786 (Why is no real title available?)
- scientific article; zbMATH DE number 3924818 (Why is no real title available?)
- scientific article; zbMATH DE number 4094840 (Why is no real title available?)
- Orbitopal fixing
- scientific article; zbMATH DE number 1942408 (Why is no real title available?)
- Un Algorithme pour la Bipartition d'un Graphe en Sous-graphes de Cardinalité Fixée
- An Updated Experimental Evaluation of Graph Bipartization Methods
- New abilities and limitations of spectral graph bisection
- A complementary column generation approach for the graph equipartition problem
- A novel graph-based partitioning algorithm for large-scale dynamical systems
- Semidefinite programming and combinatorial optimization
- Eigenvalue, quadratic programming, and semidefinite programming relaxations for a cut minimization problem
- Semidefinite approximations for quadratic programs over orthogonal matrices
- Graph partitioning: an updated survey
- A note on edge-based graph partitioning and its linear algebraic structure
- The MIN-cut and vertex separator problem
This page was built for publication: A computational study of graph partitioning
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1340061)
