Graph Partitioning [Hardcover]

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.

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

2.1. Introduction 29

2.2. Principles of the multilevel method 30

2.3. Graph coarsening 33

2.4. Partitioning of the coarsened graph 37

2.5. Uncoarsening and partitions refinement 40