Publication Date: September 2011 Hardback 384 pp.
Graph partitioning is a theoretical subject with applications in many areas, principally numerical analysis, program mapping onto parallel architectures, image segmentation, and VLSI design. Over the last 40 years, the literature has strongly increased and big improvements have been made. In this book we bring together knowledge accumulated over many years to extract both the theoretical foundations of graph partitioning and its main applications.
This book aims at describing the graph partitioning problem by presenting both methodological and applied chapters. There are three parts to the book: the first part presents graph partitioning for numerical applications, the second part presents the optimization view of graph partitioning, and the third part presents other aspects of graph partitioning.
Including new test graphs and test data, this is the first book that really focuses on the graph partitioning optimization problem both theoretically and with its main applications. It is dedicated to researchers and PhD students. Departments of computer sciences, information technology, applied mathematics and electronics would also be interested in this book.
1. General Introduction to Graph Partitioning, Charles-Edmond Bichot.
Part 1. Graph Partitioning for Numerical Analysis
2. A Partitioning Requiring Rapidity and Quality: The Multilevel Method and Partitions Refinement Algorithms, Charles-Edmond Bichot.
3. Hypergraph Partitioning, Cédric Chevalier.
4. Parallelization of Graph Partitioning, François Pellegrini.
5. Static Mapping of Process Graphs, François Pellegrini.
Part 2. Optimization Methods for Graph Partitioning
6. Local Metaheuristics and Graph Partitioning, Charles-Edmond Bichot.
7. Population Based Metaheuristics, Fusion-Fission and Graph Partitioning Optimization, Charles-Edmond Bichot.
8. Partitioning Mobile Networks into Tariff Zones, Mustapha Oughdi, Sid Lamrous, Alexandre Caminada.
9. Air Traffic Control Graph Partitioning Application, Charles-Edmond Bichot, Nicolas Durand.
Part 3. Other Approaches to Graph Partitioning
10. Application of Graph Partitioning to Image Segmentation, Amir Nakib, Laurent Najman, Hugues Talbot, Patrick Siarry.
11. Distances in Graph Partitioning, Alain Guénoche.
12. Detection of Disjoint or Overlapping Communities in Networks, Jean-Baptiste Angelelli, Alain Guénoche, Laurence Reboul.
13. Multilevel Local Optimization of Modularity, Thomas Aynaud, Vincent D. Blondel, Jean-Loup Guillaume and Renaud Lambiotte.
About the Authors
Charles-Edmond Bichot is Associate Professor at École Centrale de Lyon in France. His work always focuses on the graph partitioning optimization problem and its applications.
Patrick Siarry is Professor in automatics and informatics at Paris-Est University in France. His main research interests are the applications of new stochastic global optimization heuristics to various engineering fields.