On parallelizing graph-partitioning heuristics

DOI10.1007/BFB0032052MaRDI QIDQ4038712zbMATH OpenFDO

Authors Markus G. Wloka, John Savage

Publication date 18 May 1993

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/BFB0032052

zbMATH Keywords

\(P\)- hardKernighan-Lin heuristicNP-completeparallel heuristicsimulated annealing heuristic

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Distributed algorithms (68W15)

Recommendations

• Partitioning graphs on message-passing machines by pairwise mincut
• A parallel graph partitioning algorithm for a message-passing multiprocessor
• scientific article; zbMATH DE number 2131658
• Implementation of parallel branch-and-bound algorithms --- experiences with the graph partitioning problem
• Path optimization for graph partitioning problems

Cited in

(28)

• A parallel graph partitioning algorithm for a message-passing multiprocessor
• Implementation of parallel branch-and-bound algorithms --- experiences with the graph partitioning problem
• A comparison of clustering heuristics for scheduling directed acyclic graphs on multiprocessors
• Solving VLSI physical design problems on a vector machine
• Analysis of a heuristic for code partitioning
• New heuristic solution procedures for the uniform graph partitioning problem: Extensions and evaluation
• An experimental evaluation of local search heuristics for graph partitioning
• Graph partitioning models for parallel computing
• A mixed heuristic for circuit partitioning
• On the validity of a front-oriented approach to partitioning large sparse graphs with a connectivity constraint
• An efficient heuristic for code partitioning
• On parallelizing a greedy heuristic for finding small dominant sets
• Application of parallel and hybrid metaheuristics for graph partitioning problem
• Some graph partitioning problems
• scientific article; zbMATH DE number 2131658 (Why is no real title available?)
• A New Heuristic for Partitioning the Nodes of a Graph
• Min-cut partitioning on underlying tree and graph structures
• Parallelization domain oriented multilevel graph partitioner
• Graph partitioning with acyclicity constraints
• Solving graph partitioning problems with parallel metaheuristics
• scientific article; zbMATH DE number 3997175 (Why is no real title available?)
• scientific article; zbMATH DE number 1852148 (Why is no real title available?)
• Evaluating the Kernighan-Lin Heuristic for Hardware/Software Partitioning
• Current challenges in parallel graph partitioning
• Artificial Evolution
• Deterministic Parallel Hypergraph Partitioning
• Parallel unconstrained local search for partitioning irregular graphs
• Direct graph \(k\)-partitioning with a Kernighan-Lin like heuristic

This page was built for publication: On parallelizing graph-partitioning heuristics

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