An Algorithm for Partitioning the Nodes of a Graph

DOI10.1137/0603056zbMath0505.05050OpenAlexW2035409768MaRDI QIDQ4740598

Earl R. Barnes

Publication date: 1982

Published in: SIAM Journal on Algebraic Discrete Methods (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/0603056

zbMATH Keywords

linear programming transportation problempartitioning into disjoint subsets

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Extremal problems in graph theory (05C35) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Cites Work

• The variation of the spectrum of a normal matrix
• An Efficient Heuristic Procedure for Partitioning Graphs
• Lower Bounds for the Partitioning of Graphs
• Unnamed Item
• Unnamed Item
• Unnamed Item

Related Items (26)

Grouping of parts and components in flexible manufacturing systems ⋮ A computational study of graph partitioning ⋮ On the magnetisation of the ground states in two dimensional Ising spin glasses ⋮ EVALUATION OF AUTOMATIC DOMAIN PARTITIONING ALGORITHMS FOR PARALLEL FINITE ELEMENT ANALYSIS ⋮ Approximation techniques for hypergraph partitioning problems ⋮ Bayesian degree-corrected stochastic blockmodels for community detection ⋮ 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 ⋮ Spectral partitioning works: planar graphs and finite element meshes ⋮ On the validity of a front-oriented approach to partitioning large sparse graphs with a connectivity constraint ⋮ Graph Coloring Using Eigenvalue Decomposition ⋮ Global discriminative-based nonnegative spectral clustering ⋮ Spectral methods for graph bisection problems. ⋮ Algorithms for searching paths in huge graphs ⋮ Optimal partitions having disjoint convex and conic hulls ⋮ An algorithm to maximize the agreement between partitions ⋮ Modeling hypergraphs by graphs with the same mincut properties ⋮ A hierarchical approach for metal parts fabrication ⋮ Incremental methods for community detection in both fully and growing dynamic networks ⋮ Two-stage algorithm using influence coefficient for detecting the hierarchical, non-overlapping and overlapping community structure ⋮ Algorithms for minclique scheduling problems ⋮ Spectral partitioning with multiple eigenvectors ⋮ Algorithms for graph partitioning problems by means of eigenspace relaxations ⋮ A mini-line approach for pull production ⋮ Finding part-machine families using graph partitioning techniques ⋮ A quadratically convergent local algorithm on minimizing sums of the largest eigenvalues of a symmetric matrix

This page was built for publication: An Algorithm for Partitioning the Nodes of a Graph