Improving the Performance of the Kernighan-Lin and Simulated Annealing Graph Bisection Algorithms

Abstract

In this paper, we compare the performance of two popular graph bisection algorithms. We also present an empirical study of a new heuristic, first proposed in Bui, Chaudhuri, Leighton, Sipser that dramatically improves the performance of these bisection algorithms on graphs with small average degree. In the graph bisection problem we are given a graph G = (V,E) and are asked to partition the vertex set V into two equal-sized subsets V1 and V2 in such a way that the size of the cut between them is minimized. The cut of V1 and V2 is the number of edges with one endpoint in V1 and the other endpoint in V2. The minimum cut over all bisections is known as the bisection width of the graph. Graph bisection has applications in VLSI placement and routing problems. The problem is known to be NP-hard.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Jun 01, 1989
Accession Number
ADA211914

Entities

People

  • Christopher Heigham
  • Curt Jones
  • Thang Bui
  • Tom Leighton

Organizations

  • Massachusetts Institute of Technology

Tags

Communities of Interest

  • Materials and Manufacturing Processes

DTIC Thesaurus Topics

  • Air Force
  • Algorithms
  • Annealing
  • Computer Science
  • Computers
  • Contracts
  • Equations
  • Equations Of State
  • High Temperature
  • Low Temperature
  • Massachusetts
  • Observation
  • Probability
  • Random Number Generators
  • Standards
  • Statistical Mechanics
  • Trees (Data Structures)

Fields of Study

  • Computer science
  • Mathematics

Readers

  • Graph Algorithms and Convex Optimization.
  • Operations Research