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

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

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

• 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?)
• 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
• 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
• \(\text{BIDA}^*\): An improved perimeter search algorithm

Cited in

(6)

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

Describes a project that uses

Uses Software

• JOSTLE
• Scotch
• DIMACS
• Chaco
• PARTY

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)