Note: Not guaranteed to come with supplemental materials (access cards, study guides, lab manuals, CDs, etc.)
Extend Your Rental at Any Time
Need to keep your rental past your due date? At any time before your due date you can extend or purchase your rental through your account.
Sorry, this item is currently unavailable.
Graph partitioning is a theoretical subject with applications in many areas, principally: numerical analysis, programs mapping onto parallel architectures, image segmentation, VLSI design. During the last 40 years, the literature has strongly increased and big improvements have been made. This book brings together the knowledge accumulated during many years to extract both theoretical foundations of graph partitioning and its main applications.
Table of Contents
Introduction xiii Charles-Edmond Bichot, Patrick Siarry
Chapter 1. General Introduction to Graph Partitioning 1 Charles-Edmond Bichot
1.1. Partitioning 1
1.2. Mathematical notions 2
1.3. Graphs 4
1.4. Formal description of the graph partitioning problem 8
1.5. Objective functions for graph partitioning 11
1.6. Constrained graph partitioning 13
1.7. Unconstrained graph partitioning 14
1.8. Differences between constrained and unconstrained partitioning 16
1.9. From bisection to k-partitioning: the recursive bisection method 17
1.10. NP-hardness of graph partitioning optimization problems 19
1.11. Conclusion 22
1.12. Bibliography 22
Part 1: Graph Partitioning for Numerical Analysis 27
Chapter 2. A Partitioning Requiring Rapidity and Quality: The Multilevel Method and Partitions Refinement Algorithms 29 Charles-Edmond Bichot