Path optimization for graph partitioning problems

DOI10.1016/S0166-218X(98)00084-5zbMath0913.68153MaRDI QIDQ1276954

Jonathan W. Berry, Mark K. Goldberg

Publication date: 2 February 1999

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: http://www.elsevier.com/locate/dam

zbMATH Keywords

graph partitioningpath optimization

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10)

Related Items (3)

Vertex ordering and partitioning problems for random spatial graphs. ⋮ A semidefinite programming based polyhedral cut and price approach for the maxcut problem ⋮ Experiments on the minimum linear arrangement problem

Uses Software

• Chaco

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Optimization by Simulated Annealing
• Unit disk graphs
• A linear time algorithm for graph partition problems
• Node and edge relaxations of the max-cut problem
• A projection technique for partitioning the nodes of a graph
• .879-approximation algorithms for MAX CUT and MAX 2SAT
• The maximum concurrent flow problem
• Optimization by Simulated Annealing: An Experimental Evaluation; Part I, Graph Partitioning
• Optimization by Simulated Annealing: An Experimental Evaluation; Part II, Graph Coloring and Number Partitioning
• Finding a Maximum Cut of a Planar Graph in Polynomial Time
• An Efficient Heuristic Procedure for Partitioning Graphs
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• An Improved Spectral Graph Partitioning Algorithm for Mapping Parallel Computations
• Lower Bounds for the Partitioning of Graphs

This page was built for publication: Path optimization for graph partitioning problems