Lower bounds and exact algorithms for the graph partitioning problem using multicommodity flows / von Norbert Sensen. 2003
Inhalt
- 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