Finding optimal solutions to the graph partitioning problem with heuristic search

DOI10.1007/s10472-005-9001-2zbMath1110.68099OpenAlexW2009528260MaRDI QIDQ2502154

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

Related Items (5)

ILP-Based Local Search for Graph Partitioning ⋮ Models and methods for solving the problem of network vulnerability ⋮ Graph clustering ⋮ An exact combinatorial algorithm for minimum graph bisection ⋮ Unnamed Item

Uses Software

• JOSTLE
• Scotch
• DIMACS
• Chaco
• PARTY

Cites Work

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

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