Lower bounds and exact algorithms for the graph partitioning problem using multicommodity flows / von Norbert Sensen. 2003
Content
List of Figures, Tables and Algorithms
Introduction
Motivation
Overview of this work
Definitions
Known Lower Bounds
Exact Graph Partitioning Algorithms
Graphs for Experiments
The New Lower Bounds
Leightons Bound
VarMC- and MVarMC-Bound
Idea
Definition of Multicommodity Flows
Lower Bound based on Cut-Flow and Congestion
Definition of VarMC and MVarMC
Cut-Flow of VarMC and MVarMC
Summary and Outlook
Experimental Evaluation of the Lower Bounds
Theoretical Issues
Symmetrical Solutions
Some Specific Graphs
Bisection of the Complete Bipartite Graph Ka,b
The k-partitioning of the aa-Torus
The k-partitioning of the aa-Grid
Bisection of the Butterfly
Bisection of the Beneš Network
The k-partitioning of the Hypercube Q(d)
Summary
Upper Bounds on the Lower Bounds
Computation of the Lower Bounds
Branch & Bound Algorithm
Upper Bound and Depth-First-Search
Realization of Branchings
Variable Fixing
Branching Selection
Prediction of the Impact of a Split on the Lower Bound
Prediction of the Impact of a Join on the Lower Bound
Making the Branching Selection based on Predictions for the Lower Bound
Experimental Evaluation
Conclusion
Bibliography
Details of Experimental Results