Finding optimal solutions to the graph partitioning problem with heuristic search

DOI10.1007/S10472-005-9001-2zbMATH Open1110.68099OpenAlexW2009528260MaRDI QIDQ2502154FDOQ2502154

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

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

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)

Cites Work

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

Cited In (6)

• An exact combinatorial algorithm for minimum graph bisection
• Models and methods for solving the problem of network vulnerability
• An experimental evaluation of local search heuristics for graph partitioning
• Title not available (Why is that?)
• Graph clustering
• ILP-Based Local Search for Graph Partitioning

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)