Graph Bisection Algorithms with Good Average Case Behavior

We describe a polynomial time algorithm that, for every input graph, either outputs the minimum bisection of the graph or halts without output. More importantly, we show that the algorithm chooses the former course with high probability for many natural classes of graphs. In particular, for every fixed d⩾3, all suffciently large n and all b = o(n 1-(1/[(d+1)/2]), the algorithm finds the minimum bisection for almost all d-regular labelled simple graphs with 2n nodes and bisection width b.

Authors

• Thang Nguyen Bui
• Soma Chaudhuri
• Frank Thomson Leighton
• Michael Sipser

Keywords

• Computer aided software engineering
• Approximation algorithms
• Routing
• Wires
• Mathematics
• Computer science
• Polynomials
• Graph Partitioning
• Heuristic
• Natural Classification
• Simple Graph
• Class Of Graphs
• Loss Of Generality
• Proof Of Theorem
• End Of Phase
• Simulated Annealing
• Pair Of Nodes
• Probability 1
• Random Graph
• Multiple Edges
• Simulated Annealing Algorithm
• Behavior Of Algorithm
• Flow Algorithm
• Cut Set
• Graph Algorithms
• Number Of Graphs
• Small Graphs
• Planar Graphs