A computational study of graph partitioning

DOI10.1007/BF01581147zbMath0830.90130OpenAlexW1999285709MaRDI QIDQ1340061

Julie Falkner, Franz Rendl, Henry Wolkowicz

Publication date: 11 December 1994

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf01581147

zbMATH Keywords

graph partitioningquadratic 0-1 programmingeigenvalue-based technique

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Boolean programming (90C09)

Related Items

Un Algorithme pour la Bipartition d'un Graphe en Sous-graphes de Cardinalité Fixée, A projection technique for partitioning the nodes of a graph, Semidefinite approximations for quadratic programs over orthogonal matrices, Orbitopal fixing, An exact algorithm for graph partitioning, Spectral methods for graph bisection problems., Semidefinite programming relaxations for the graph partitioning problem, The MIN-cut and vertex separator problem, Semidefinite programming and combinatorial optimization, Eigenvalue, quadratic programming, and semidefinite programming relaxations for a cut minimization problem, Unnamed Item, Spectral partitioning with multiple eigenvectors, Algorithms for graph partitioning problems by means of eigenspace relaxations, An optimal tree search method for the manufacturing systems cell formation problem, Spectral bounds for graph partitioning with prescribed partition sizes, Semidefinite programming and eigenvalue bounds for the graph partition problem

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• \(\lambda_ 1\), isoperimetric inequalities for graphs, and superconcentrators
• A MIMD implementation of a parallel Euler solver for unstructured grids
• More bounds for eigenvalues using traces
• Optimal linear labelings and eigenvalues of graphs
• A projection technique for partitioning the nodes of a graph
• The equipartition polytope. I: Formulations, dimension and basic facets
• Optimization by Simulated Annealing: An Experimental Evaluation; Part I, Graph Partitioning
• Matrix Analysis
• A New Heuristic 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 Efficient Heuristic Procedure for Partitioning Graphs
• An Algorithm for Partitioning the Nodes of a Graph
• Lower Bounds for the Partitioning of Graphs