de
en
Close
Detailsuche
Bibliotheken
Projekt
Imprint
Privacy Policy
Close
Publizieren
Besondere Sammlungen
Digitalisierungsservice
Hilfe
Impressum
Datenschutz
jump to main content
Search Details
Quicksearch:
OK
Result-List
Title
Title
Content
Content
Page
Page
Search Book
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
Classical Spectral Method
Improved Spectral Methods
Semidefinite programming
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
The Experiments
Bisection Problems
k-partitioning Problems
Graph Partitioning Problems with k=2 and M=23n
Summary
Theoretical Issues
Symmetrical Solutions
Definitions
Existence of Optimal and Symmetrical MC-solutions
Some Implications
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
Linear Programming
Cost Decomposition
Column Generation
Lagrangian Relaxation based Column Generation
Approximation Algorithm
Literature and Idea
The Approximation Algorithm
Implementation Details
Experimental Evaluations
Cost-Decomposition
Approximation Algorithm
Comparison of the different Methods
Summary
Branch & Bound Algorithm
Upper Bound and Depth-First-Search
Realization of Branchings
Variable Fixing
Simple Considerations
MC-bounds based Methods
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
The search-operation requires javascript to be activated.