An Efficient Heuristic Procedure for Partitioning Graphs

DOI10.1002/j.1538-7305.1970.tb01770.xzbMath0333.05001OpenAlexW2161455936WikidataQ56431136 ScholiaQ56431136MaRDI QIDQ4100093

No author found.

Publication date: 1970

Published in: Bell System Technical Journal (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1002/j.1538-7305.1970.tb01770.x

Mathematics Subject Classification ID

Graph theory (05C99) Software, source code, etc. for problems pertaining to combinatorics (05-04)

Related Items

On the statistical detection of clusters in undirected networks, Leveraging special-purpose hardware for local search heuristics, Weighted modularity optimization for crisp and fuzzy community detection in large-scale networks, Evolutionary algorithm and modularity for detecting communities in networks, Multiway \(p\)-spectral graph cuts on Grassmann manifolds, Genetic search algorithms and their randomized operators, Graph coarsening: from scientific computing to machine learning, The partition problem, Multi-way graph partition by stochastic probe, Network bipartitioning in the anti-communicability Euclidean space, Normalized discrete Ricci flow used in community detection, The multi-layered network design problem, Problems of discrete optimization: challenges and main approaches to solve them, Face recognition using spectral features, Distributed integral column generation for set partitioning problems, An overview of graph covering and partitioning, Parallel mesh-partitioning algorithms for generating shape optimised partitions using evolutionary computing, Congestion attacks in payment channel networks, A survey of kernel and spectral methods for clustering, Some new classes of facets for the equicut polytope, Solving the max-cut problem using eigenvalues, A very large-scale neighborhood search algorithm for the multi-resource generalized assignment problem, Factoring Boolean functions using graph partitioning, The Boolean quadratic programming problem with generalized upper bound constraints, A parallel local search framework for the fixed-charge multicommodity network flow problem, An effective iterated tabu search for the maximum bisection problem, Exact computational solution of modularity density maximization by effective column generation, Increasing the attraction area of the global minimum in the binary optimization problem, A variable-depth search algorithm for the recursive bipartitioning of signal flow graphs, A simple approach to sparse clustering, A new approach to minimising the frontwidth in finite element calculations, Fuzzy random walkers with second order bounds: an asymmetric analysis, Minimum-perimeter domain assignment, Moving clusters within a memetic algorithm for graph partitioning, A new unifying heuristic algorithm for the undirected minimum cut problems using minimum range cut algorithms, Combining simulated annealing with local search heuristics, Tabu search for graph partitioning, On the validity of a front-oriented approach to partitioning large sparse graphs with a connectivity constraint, Partitioning mathematical programs for parallel solution, Parallel local search, Test driving three 1995 genetic algorithms: New test functions and geometric matching, A new extension of local search applied to the Dial-A-Ride problem, An approximation algorithm for graph partitioning via deterministic annealing neural network, A novel partitioning method for block-structured adaptive meshes, Beyond good partition shapes: an analysis of diffusive graph partitioning, Social network community detection using agglomerative spectral clustering, A novel probabilistic clustering model for heterogeneous networks, Evolutionary optimization and the estimation of search distributions with applications to graph bipartitioning., A new greedy algorithm for the quadratic assignment problem, Parallel three-dimensional direct simulation Monte Carlo method and its applications., Spectral methods for graph bisection problems., Linear and quadratic programming approaches for the general graph partitioning problem, Semidefinite programming relaxations for the graph partitioning problem, An exact approach for the multi-constraint graph partitioning problem, Reformulated acyclic partitioning for rail-rail containers transshipment, An efficient local search for the feedback vertex set problem, Online partitioning method for decentralized control of linear switching large-scale systems, A GRASP-Tabu heuristic approach to territory design for pickup and delivery operations for large-scale instances, Efficient modularity density heuristics for large graphs, Extended neighborhood: Definition and characterization, A graph partitioning strategy for solving large-scale crew scheduling problems, Integral simplex using double decomposition for set partitioning problems, Stochastic block models are a discrete surface tension, Optimized quantum circuit partitioning, Detecting overlapping communities in networks using the maximal sub-graph and the clustering coefficient, Two-stage algorithm using influence coefficient for detecting the hierarchical, non-overlapping and overlapping community structure, Uncovering the overlapping community structure of complex networks by maximal cliques, Detecting community structure via the maximal sub-graphs and belonging degrees in complex networks, Reduction techniques for network validation in systems biology, A practical propagation path identification scheme for quality-related faults based on nonlinear dynamic latent variable model and partitioned Bayesian network, Block-insertion-based algorithms for the linear ordering problem, Efficient semidefinite branch-and-cut for MAP-MRF inference, Paroid search: Generic local combinatorial optimization, Profile likelihood biclustering, Exploiting special structure in a primal-dual path-following algorithm, Greedy randomized adaptive search procedures, An adaptive granulation algorithm for community detection based on improved label propagation, An evolutionary approach to optimizing teleportation cost in distributed quantum computation, Overlapping communities and roles in networks with node attributes: probabilistic graphical modeling, Bayesian formulation and variational inference, Partitioning graphs on message-passing machines by pairwise mincut, Towards quantum computing based community detection, Multilevel graph partitioning for three-dimensional discrete fracture network flow simulations, Computing in combinatorial optimization, Dynamic load balancing in computational mechanics, Generating irregular partitionable data structures, Algorithms for graph partitioning problems by means of eigenspace relaxations, Spectral bounds for graph partitioning with prescribed partition sizes, Simultaneous mesh generation and partitioning for Delaunay meshes, Congress seat allocation using mathematical optimization, Intercode hexahedral meshing from Eulerian to Lagrangian simulations, A decomposition-based approach for the multiperiod multiproduct distribution planning problem, The effect of graph partitioning techniques on parallel block FSAI preconditioning: a computational study, Local search algorithms for the multiprocessor flow shop scheduling problem, Graph multidimensional scaling with self-organizing maps, Modified modularity density maximization and density ratio heuristic, The GST load balancing algorithm for parallel and distributed systems, Speeding up a memetic algorithm for the max-bisection problem, Solution of large weighted equicut problems, On local search for the generalized graph coloring problem, Global optimization of nonconvex problems with multilinear intermediates, Continuous quadratic programming formulations of optimization problems on graphs, The linear ordering problem revisited, Parallel static and dynamic multi‐constraint graph partitioning, EVALUATION OF AUTOMATIC DOMAIN PARTITIONING ALGORITHMS FOR PARALLEL FINITE ELEMENT ANALYSIS, Unnamed Item, Un Algorithme pour la Bipartition d'un Graphe en Sous-graphes de Cardinalité Fixée, The equipartition polytope. I: Formulations, dimension and basic facets, A Social Network Based Patching Scheme for Worm Containment in Cellular Networks, The optimal partitioning of networks, AN EFFECTIVE APPROACH FOR DISTRIBUTED PROGRAM ALLOCATION, Local bipartite turán graphs and graph partitioning, Parallel adaptive multigrid methods in plane linear elasticity problems, Via Minimization with Pin Preassignments and Layer Preference, Partitioning methods for satisfiability testing on large formulas, A class of bounded approximation algorithms for graph partitioning, Local search for load balancing problems for servers with large dimension, Minimum bisection is NP-hard on unit disk graphs, Identifying influential links to control spreading of epidemics, Local search for constrained graph clustering in biological networks, Branch-and-bound techniques for the maximum planar subgraph problem^∗, On using learning automata for fast graph partitioning, A hybrid algorithm for the drilling rig routing problem, Very Large-Scale Neighborhood Search: Overview and Case Studies on Coloring Problems, A bubble-inspired algorithm for finite element mesh partitioning, On algorithms in the parallel design of logic and layout of circuits with functional blocks, A reactive self-tuning scheme for multilevel graph partitioning, A dynamic programming approach for distributing quantum circuits by bipartite graphs, A polyhedral study of lifted multicuts, Linear arrangement problems on recursively partitioned graphs, Improving Unstructured Mesh Partitions for Multiple Criteria Using Mesh Adjacencies, An Efficient Semidefinite Programming Relaxation for the Graph Partition Problem, Core-periphery structure in networks: a statistical exposition, Detecting communities in \(K\)-partite \(K\)-uniform (hyper)networks, Linear placement algorithms and applications to VLSI design, Solving Graph Partitioning Problems with Parallel Metaheuristics, Structure Detection in Mixed-Integer Programs, Quadratic 0–1 programming: Tightening linear or quadratic convex reformulation by use of relaxations, Decentralized mining social network communities with agents, Load-Balancing for Parallel Delaunay Triangulations, State-of-the-Art Sparse Direct Solvers, A GENETIC ALGORITHM FOR DETECTING COMMUNITIES IN LARGE-SCALE COMPLEX NETWORKS, COMPILE-TIME ANALYSIS AND OPTIMIZATION OF EXPLICITLY PARALLEL PROGRAMS*, Finding network communities using modularity density, Multi-level spectral graph partitioning method, Finding optimal hardware/software partitions, An experimental study of variable depth search algorithms for the quadratic assignment problem, A new method, the fusion fission, for the relaxed \(k\)-way graph partitioning problem, and comparisons with some multilevel algorithms, An efficient approach for large scale graph partitioning, Mixed-Integer Programming for Cycle Detection in Nonreversible Markov Processes, Vehicle Routing Problems with Inter-Tour Resource Constraints, A global method for the limited K‐partitioning of hypergraphs representing optimal design problems in complex machine systems, Adaptive Anisotropic Unstructured Mesh Generation Method Based on Fluid Relaxation Analogy, Algorithms for the \(q\)-model clustering problem with application in switching cabinet manufacturing, Unique optimal solution instance and computational complexity of backbone in the graph bi-partitioning problem, Unnamed Item, Sequential search and its application to vehicle-routing problems, A first multilevel cooperative algorithm for capacitated multicommodity network design, An annotated bibliography of combinatorial optimization problems with fixed cardinality constraints, Heuristic and simulated annealing algorithms for solving extended cell assignment problem in wireless ATM networks, Multiperiod network design with incremental routing, Community Detection in Networks via Nonlinear Modularity Eigenvectors, Adapting Iterative-Improvement Heuristics for Scheduling File-Sharing Tasks on Heterogeneous Platforms, Reducing Rollbacks Through Partitioning in PCS Parallel Simulation, Combinatorial Aspects in Sparse Elimination Methods, Simplified Energy Landscape for Modularity Using Total Variation, A semidefinite programming based polyhedral cut and price approach for the maxcut problem, Relaxation-Based Coarsening for Multilevel Hypergraph Partitioning, Force-based incremental algorithm for mining community structure in dynamic network, SDP Relaxations for Some Combinatorial Optimization Problems, Efficient geo-graph contiguity and hole algorithms for geographic zoning and dynamic plane graph partitioning, Evaluating the quality of image matrices in blockmodeling, Combined neighborhood tabu search for community detection in complex networks, A hybrid artificial immune network for detecting communities in complex networks, Parallel DSMC method using dynamic domain decomposition, Network community detection using modularity density measures, Evaluation of a Flow-Based Hypergraph Bipartitioning Algorithm, Optimal clustering structures for hierarchical topological design of large computer networks, A framework for clustering massive graph streams, A classification for community discovery methods in complex networks, Optimal placement of valves in a water distribution network with CLP(FD), Partitioning a reaction–diffusion ecological network for dynamic stability, Summary and Semi-average Similarity Criteria for Individual Clusters, Community detection based on network communicability, Parallel Implementation of DSMC Using Unstructured Mesh, COMMUNITY DETECTION IN SOCIAL NETWORKS EMPLOYING COMPONENT INDEPENDENCY, Efficient Matching for Column Intersection Graphs, A TWO-STATE ANT COLONY ALGORITHM FOR SOLVING THE MINIMUM GRAPH BISECTION PROBLEM, Toward Optimal Community Detection: From Trees to General Weighted Networks, The bisection width of cubic graphs, Unnamed Item, Unnamed Item, Unnamed Item, An Algorithm for Partitioning the Nodes of a Graph, Unnamed Item, Engineering Branch-and-Cut Algorithms for the Equicut Problem, Fast local search algorithms for the handicapped persons transportation problem, Unnamed Item, A discrete dynamic convexized method for VLSI circuit partitioning, Time optimal consensus tracking with multiple leaders, Network Flow-Based Refinement for Multilevel Hypergraph Partitioning, Randomized algorithms in combinatorial optimization: A survey, Grouping of parts and components in flexible manufacturing systems, Language games in investigation of social networks: finding communities and influential agents, A deterministic annealing algorithm for approximating a solution of the min-bisection problem, A decomposition algorithm for multi-terminal network flows, Community detection via an efficient nonconvex optimization approach based on modularity, Communicability graph and community structures in complex networks, A fuzzy clustering algorithm for graph bisection, A computational study of graph partitioning, A unified framework of multi-objective cost functions for partitioning unstructured finite element meshes, New heuristic solution procedures for the uniform graph partitioning problem: Extensions and evaluation, Genetic algorithm based heuristics for the mapping problem, On the magnetisation of the ground states in two dimensional Ising spin glasses, A three-phased local search approach for the clique partitioning problem, Classification of applied methods of combinatorial optimization, Transformation of energy landscape in the problem of binary minimization, Bayesian degree-corrected stochastic blockmodels for community detection, A HW/SW partitioner for multi-mode multi-task embedded applications, A linear programming approach to reasoning about probabilities, Multicuts and perturb \& MAP for probabilistic graph clustering, Polyhedral combinatorics of the \(K\)-partitioning problem with representative variables, Community detection by modularity maximization using GRASP with path relinking, A branch-and-bound algorithm for the acyclic partitioning problem, Multi-product valid inequalities for the discrete lot-sizing and scheduling problem, Cluster differences scaling with a within-clusters loss component and a fuzzy successive approximation strategy to avoid local minima, Partitioning of sequentially ordered systems using linear programming, A polynomial characterization of some graph partitioning problems, How easy is local search?, A parallel graph partitioning algorithm for a message-passing multiprocessor, Logical and layout structures of documents, Continuous reductions among combinatorial optimization problems, Distributed CSPs by graph partitioning, A model-based approach and analysis for multi-period networks, Direct graph \(k\)-partitioning with a Kernighan-Lin like heuristic, Using domain decomposition to find graph bisectors, A new approach to choosing initial points in local search, A branch-and-cut algorithm for the equicut problem, Performance of a genetic algorithm for the graph partitioning problem, A network flow model of group technology, Autocorrelation coefficient for the graph bipartitioning problem, Efficient algorithms for single- and two-layer linear placement of parallel graphs, On sparse matrix orderings in interior point methods, The unconstrained binary quadratic programming problem: a survey, An effective multilevel tabu search approach for balanced graph partitioning, Projection approaches to process mining using region-based techniques, Iterative denoising, A benchmark library and a comparison of heuristic methods for the linear ordering problem, Hybridizing evolutionary algorithms with variable-depth search to overcome local optima, Parallel multilevel algorithms for hypergraph partitioning, Multi-level direct \(K\)-way hypergraph partitioning with multiple constraints and fixed vertices, Hearing the clusters of a graph: A distributed algorithm, Hypercube embedding heuristics: An evaluation, A variable depth search branching, Graph clustering, A multidimensional and multimembership clustering method for social networks and its application in customer relationship management, Randomized local search for the discrete competitive facility location problem, Co-clustering documents and words by minimizing the normalized cut objective function, Separation of variables for function generated high-order tensors, Complexity of local search for the \(p\)-median problem, Automatic symbolic compositional verification by learning assumptions, Implementation of parallel branch-and-bound algorithms --- experiences with the graph partitioning problem, Preprocessing for a map sectorization problem by means of mathematical programming, Book review of: B. Goldengorin et al., Cell formation in industrial engineering. Theory, algorithms and experiments, The decomposition of a communication network considering traffic demand interrelations, Generalizations of Opt P to the polynomial hierarchy, Nested annealing: A provable improvement to simulated annealing, Maximum concurrent flows and minimum cuts, The geo-graph in practice: creating United States congressional districts from census blocks, The MIN-cut and vertex separator problem, A multilevel bilinear programming algorithm for the vertex separator problem, Finding good approximate vertex and edge partitions is NP-hard, The robust binomial approach to chance-constrained optimization problems with application to stochastic partitioning of large process networks, New \(({\Delta{}}, D)\) graphs discovered by heuristic search, Paroids: A canonical format for combinatorial optimization, Parallel adaptation of general three-dimensional hybrid meshes, A survey of very large-scale neighborhood search techniques, Fast and accurate determination of modularity and its effect size, A MIMD implementation of a parallel Euler solver for unstructured grids, Parallel finite element simulations of incompressible viscous fluid flow by domain decomposition with Lagrange multipliers, A Matrix Partitioning Interface to PaToH in MATLAB, Identifying sets of key players in a social network, Mathematical methods for physical layout of printed circuit boards: an overview, A novel iterative shape from focus algorithm based on combinatorial optimization, Optimizing teleportation cost in distributed quantum circuits, A Lagrangean heuristic for the maximal covering location problem, The life span method -- a new variant of local search, Path optimization for graph partitioning problems, An efficient memetic algorithm for the graph partitioning problem, Optimal block-tridiagonalization of matrices for coherent charge transport, The node capacitated graph partitioning problem: A computational study, An effective local search for the maximum clique problem, An optimal tree search method for the manufacturing systems cell formation problem, An improved spectral clustering community detection algorithm based on probability matrix, Optimal cutting directions and rectangle orientation algorithm, A framework for solving VLSI graph layout problems, Exact solution of multicommodity network optimization problems with general step cost functions, A heuristic method for solving the problem of partitioning graphs with supply and demand, Control abstractions for local search, ``Miniaturized linearizations for quadratic 0/1 problems, A genetic algorithm approach for regrouping service sites, Multilevel approaches for large-scale proteomic networks, Evaluating the Kernighan-Lin Heuristic for Hardware/Software Partitioning, ILP-Based Local Search for Graph Partitioning, Mixture models and networks: The stochastic blockmodel, The <scp>K‐partitioning</scp> problem: Formulations and <scp>branch‐and‐cut</scp>, Faster exact solution of sparse maxcut and QUBO problems, Mixed integer bilevel optimization with a \(k\)-optimal follower: a hierarchy of bounds, Multivariate spatio‐temporal modelling for assessing Antarctica's present‐day contribution to sea‐level rise, Orchard algorithm (OA): a new meta-heuristic algorithm for solving discrete and continuous optimization problems, Balanced graph partitioning based on mixed 0-1 linear programming and iteration vertex relocation algorithm, Quasi-Monte Carlo Methods for Binary Event Models with Complex Family Data, Linear precedence functions for weak precedence grammars, A survey of direct methods for sparse linear systems, How to divide a catchment to conquer its parallel processing. An efficient algorithm for the partitioning of water catchments, Influence-based model decomposition for reasoning about spatially distributed physical systems, Performance of simulated annealing-based heuristic for the unconstrained binary quadratic programming problem, Parallel dynamic load balancing strategies for adaptive irregular applications, Multiphase mesh partitioning, Semidefinite relaxations for partitioning, assignment and ordering problems, Semidefinite relaxations for partitioning, assignment and ordering problems, Airspace sectorization with constraints, Multilevel Algorithms for Acyclic Partitioning of Directed Acyclic Graphs, Unnamed Item, A GRAPH BASED DAVIDSON ALGORITHM FOR THE GRAPH PARTITIONING PROBLEM, Communication Avoiding ILU0 Preconditioner, Scalable module detection for attributed networks with applications to breast cancer, PMORSy: parallel sparse matrix ordering software for fill-in minimization