ILP-Based Local Search for Graph Partitioning

DOI10.1145/3398634MaRDI QIDQ6039924zbMATH OpenOpenAlexFDO

Authors Alexandra Henzinger, Alexander Noe, Christian Schulz

Publication date 23 May 2023

Published in ACM Journal of Experimental Algorithmics (Search for Journal in Brave)

Full work available at URL https://drops.dagstuhl.de/opus/volltexte/2018/8939/

zbMATH Keywords

balanced graph partitioningevolutionary algorithminteger linear programminglocal search algorithm

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Evolutionary algorithms, genetic algorithms (computational aspects) (68W50) Integer programming (90C10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Recommendations

• scientific article; zbMATH DE number 7286677
• An efficient memetic algorithm for the graph partitioning problem
• An effective multilevel tabu search approach for balanced graph partitioning
• Engineering multilevel graph partitioning algorithms
• Local metaheuristics and graph partitioning

Cites work

• scientific article; zbMATH DE number 1875431 (Why is no real title available?)
• scientific article; zbMATH DE number 7286677 (Why is no real title available?)
• 10.1162/153244303321897735
• A Comparative Study of Linear and Semidefinite Branch-and-Cut Methods for Solving the Minimum Graph Bisection Problem
• A Fast and High Quality Multilevel Scheme for Partitioning Irregular Graphs
• A combined evolutionary search and multilevel optimisation approach to graph-partitioning
• An Automatic Method of Solving Discrete Programming Problems
• An Efficient Heuristic Procedure for Partitioning Graphs
• An \(\mathcal{O}(n^4)\) time algorithm to compute the bisection width of solid grid graphs
• An efficient memetic algorithm for the graph partitioning problem
• An exact algorithm for graph partitioning
• Better Bounds for Graph Bisection
• Engineering multilevel graph partitioning algorithms
• Exact combinatorial branch-and-bound for graph bisection
• Finding good approximate vertex and edge partitions is NP-hard
• Finding optimal solutions to the graph partitioning problem with heuristic search
• Graph partitioning
• Graph partitioning using linear and semidefinite programming
• Multicommodity flow approximation used for exact graph partitioning
• Nested Dissection of a Regular Finite Element Mesh
• Partitioning graphs to speedup Dijkstra's algorithm
• Recent directions in netlist partitioning: a survey
• Redundant constraints in the standard formulation for the clique partitioning problem
• Solving Graph Bisection Problems with Semidefinite Programming
• Spectral partitioning with multiple eigenvectors
• The University of Florida sparse matrix collection
• The node capacitated graph partitioning problem: A computational study

Cited in

(9)

• scientific article; zbMATH DE number 7084713 (Why is no real title available?)
• Lock-gain based graph partitioning
• Balanced graph partitioning based on mixed 0-1 linear programming and iteration vertex relocation algorithm
• Scalable high-quality hypergraph partitioning
• Flow-Based Algorithms for Improving Clusters: A Unifying Framework, Software, and Performance
• An experimental evaluation of local search heuristics for graph partitioning
• Exact vertex migration model of graph partitioning based on mixed 0-1 linear programming and iteration algorithm
• scientific article; zbMATH DE number 7286677 (Why is no real title available?)
• Parallel unconstrained local search for partitioning irregular graphs

This page was built for publication: ILP-Based Local Search for Graph Partitioning

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6039924)