A flow-based method for improving the
expansion or conductance of graph cuts

Kevin Lang (Yahoo), Satish Rao (UCB)

• Graph Partitioning Metrics
• Graph Partitioning Methods
• A Decision Problem
• The MQI lemma
• MQI algorithm
• Interpretation
• Combining a bisection heuristic and MQI
• How to fool it
• Robust in practice
• Geometric graphs
• Spectral and Metis+MQI on four IR tasks
• Debruijn Graphs
• Benchmarks from Graph Partitioning Archive
• Results for Graph Partitioning Archive
• Block Diagrams of Spectral and Metis+MQI

This document was translated from L^AT_EX by H^EV^EA and H^AC^HA.