Finding optimal solutions to the graph partitioning problem with heuristic search

DOI10.1007/S10472-005-9001-2MaRDI QIDQ2502154zbMATH OpenOpenAlexFDO

Authors Ariel Felner

Publication date 12 September 2006

Published in Annals of Mathematics and Artificial Intelligence (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s10472-005-9001-2

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20)

Recommendations

• A combined evolutionary search and multilevel optimisation approach to graph-partitioning
• An experimental evaluation of local search heuristics for graph partitioning
• Tabu search for graph partitioning
• Artificial Evolution
• New heuristic solution procedures for the uniform graph partitioning problem: Extensions and evaluation

Cites work

• \(\text{BIDA}^*\): An improved perimeter search algorithm
• A branch-and-cut algorithm for the equicut problem
• An upper bound on the time complexity of iterative-deepening-\(A^*\)
• Depth-first iterative-deepening: An optimal admissible tree search
• Disjoint pattern database heuristics
• Generalized best-first search strategies and the optimality of A*
• Genetic algorithm and graph partitioning
• Graph partitioning using learning automata
• Heuristic search in restricted memory
• scientific article; zbMATH DE number 4162303 (Why is no real title available?)
• scientific article; zbMATH DE number 1941662 (Why is no real title available?)
• scientific article; zbMATH DE number 1875431 (Why is no real title available?)
• scientific article; zbMATH DE number 2243373 (Why is no real title available?)
• Implementation of parallel branch-and-bound algorithms --- experiences with the graph partitioning problem
• Min-cut clustering
• New heuristic solution procedures for the uniform graph partitioning problem: Extensions and evaluation
• Optimization by Simulated Annealing: An Experimental Evaluation; Part I, Graph Partitioning
• Performance of linear-space search algorithms
• Sokoban: Enhancing general single-agent search methods using domain knowledge
• Solving Graph Bisection Problems with Semidefinite Programming
• Some simplified NP-complete graph problems
• The node capacitated graph partitioning problem: A computational study

Cited in

(6)

• An experimental evaluation of local search heuristics for graph partitioning
• Models and methods for solving the problem of network vulnerability
• Graph clustering
• scientific article; zbMATH DE number 7286677 (Why is no real title available?)
• ILP-Based Local Search for Graph Partitioning
• An exact combinatorial algorithm for minimum graph bisection

Describes a project that uses

Uses Software

• DIMACS
• JOSTLE
• PARTY
• Scotch
• Chaco

This page was built for publication: Finding optimal solutions to the graph partitioning problem with heuristic search

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