Graph partitioning / edited by Charles-Edmond Bichot, Patrick Siarry.
| Other author | Bichot, Charles-Edmond. |
| Other author | Siarry, Patrick. |
| Format | Book |
| Publication Info | London : ISTE ; Hoboken, NJ : Wiley, 2011. |
| Description | xv, 368 pages : illustrations, maps ; 24 cm |
| Supplemental Content | Publisher description |
| Subjects |
| Contents | Machine generated contents note: ch. 1 General Introduction to Graph Partitioning / Charles-Edmond Bichot -- 1.1.Partitioning -- 1.2.Mathematical notions -- 1.3.Graphs -- 1.4.Formal description of the graph partitioning problem -- 1.5.Objective functions for graph partitioning -- 1.6.Constrained graph partitioning -- 1.7.Unconstrained graph partitioning -- 1.8.Differences between constrained and unconstrained partitioning -- 1.9.From bisection to k-partitioning: the recursive bisection method -- 1.9.1.Creating a partition with a number of parts a power of 2, from a graph bisection algorithm -- 1.9.2.Creating a k-partition from a graph bisection algorithm using the partitioning balance -- 1.10.NP-hardness of graph partitioning optimization problems -- 1.10.1.The case of constrained graph partitioning -- 1.10.2.The case of unconstrained graph partitioning -- 1.11.Conclusion -- 1.12.Bibliography -- pt. 1 Graph Partitioning for Numerical Analysis -- ch. 2 A Partitioning Requiring Rapidity And Quality: The Multilevel Method And Partitions Refinement Algorithms / Charles-Edmond Bichot -- 2.1.Introduction -- 2.2.Principles of the multilevel method -- 2.3.Graph coarsening -- 2.3.1.Introduction -- 2.3.2.Graph matching -- 2.3.3.Hendrickson-Leland coarsening algorithm -- 2.3.4.The Heavy Edge Matching (HEM) algorithm -- 2.4.Partitioning of the coarsened graph -- 2.4.1.State-of-the-art partitioning methods -- 2.4.2.Region growing methods -- 2.5.Uncoarsening and partitions refinement -- 2.5.1.Presentation of the uncoarsening and refinement phase -- 2.5.2.The Kernighan-Lin algorithm -- 2.5.3.Fiduccia-Mattheyses implementation -- 2.5.4.Adaptation to direct k-partitioning -- 2.5.5.Global Kernighan-Lin Refinement -- 2.5.6.The Walshaw-Cross refinement algorithm -- 2.6.The spectral method -- 2.6.1.Presentation -- 2.6.2.Some results of numerical system -- 2.6.3.Finding the eigenvalues of the Laplacian matrix of a graph -- 2.6.4.Lower bound for constrained graph partitioning -- 2.6.5.Spectral methods for contrained partitioning -- 2.6.6.Spectral methods for unconstrained graph partitioning -- 2.6.7.Problems and improvements -- 2.7.Conclusion -- 2.8.Bibliography -- ch. 3 Hypergraph Partitioning / Cedric Chevalier -- 3.1.Definitions and metrics -- 3.1.1.Hypergraph and partitioning -- 3.1.2.Metrics for hypergraph partitioning -- 3.2.Connections between graphs, hypergraphs, and matrices -- 3.3.Algorithms for hypergraph partitioning -- 3.3.1.Coarsening -- 3.3.2.Initial partitioning and uncoarsening and refinement -- 3.3.3.Uncoarsening and refinement -- 3.4.Purpose -- 3.4.1.Hypergraph partitioning benefits -- 3.4.2.Matrix partitioning -- 3.4.3.Practical results -- 3.4.4.Repartitioning -- 3.4.5.Use of hypergraphs within a mesh partitioning context -- 3.4.6.Other applications -- 3.5.Conclusion -- 3.6.Software references -- 3.7.Bibliography -- ch. 4 Parallelization Of Graph Partitioning / Francois Pellegrini -- 4.1.Introduction -- 4.1.1.Need for parallelism -- 4.1.2.Multilevel framework -- 4.2.Distributed data structures -- 4.3.Parallelization of the coarsening phase -- 4.3.1.Construction of the coarse graph -- 4.3.2.Parallel matching algorithms -- 4.3.3.Collision reduction at process level -- 4.3.4.Collision reduction at vertex level -- 4.4.Folding -- 4.5.Centralization -- 4.6.Parallelization of the refinement phase -- 4.6.1.Parallelization of the local refinement methods -- 4.6.2.Band graphs -- 4.6.3.Multi-centralization -- 4.6.4.Parallelization of the global refinement methods -- 4.7.Experimental results -- 4.8.Conclusion -- 4.9.Bibliography -- ch. 5 Static Mapping Of Process Graphs / Francois Pellegrini -- 5.1.Introduction -- 5.2.Static mapping models -- 5.2.1.Cost functions -- 5.2.2.Heterogeneity of target architectures -- 5.3.Exact algorithms -- 5.4.Approximation algorithms -- 5.4.1.Global methods -- 5.4.2.Recursive methods -- 5.5.Conclusion -- 5.6.Bibliography -- pt. 2 Optimization Methods for Graph Partitioning -- ch. 6 Local Metaheuristics And Graph Partitioning / Charles-Edmond Bichot -- 6.1.General introduction to metaheuristics -- 6.2.Simulated annealing -- 6.2.1.Description of the simulated annealing algorithm -- 6.2.2.Adaptation of simulated annealing to the graph bisection problem -- 6.2.3.Generalizing this adaptation to k-partitioning -- 6.2.4.Assessment of simulated annealing adaptation to graph partitioning -- 6.3.Iterated local search -- 6.3.1.Presentation of iterated local search -- 6.3.2.Simple adaptation of iterated local search to graph partitioning -- 6.3.3.Iterated local search and multilevel method -- 6.4.Other local search metaheuristics -- 6.4.1.Greedy algorithms -- 6.4.2.Tabu search -- 6.5.Conclusion -- 6.6.Bibliography -- ch. 7 Population-based Metaheuristics, Fusion-Fission and Graph Partitioning Optimization / Charles-Edmond Bichot -- 7.1.Ant colony algorithms -- 7.2.Evolutionary algorithms -- 7.2.1.Genetic algorithms -- 7.2.2.Standard process of genetic algorithm adaptation to graph partitioning -- 7.2.3.The GA's adaptation to graph bisection optimization of Bui and Moon -- 7.2.4.Multilevel evolutionary algorithm of Soper-Walshaw-Cross -- 7.2.5.Other adaptations of evolutionary algorithms to graph partitioning optimization -- 7.3.The fusion-fission method -- 7.3.1.Introduction -- 7.3.2.Fusion-fission method principles -- 7.3.3.Algorithm -- 7.3.4.Selection of the multilevel algorithm -- 7.3.5.Creation of the sequence of number of parts -- 7.3.6.Selection of the refinement algorithm -- 7.3.7.Evaluation -- 7.4.Conclusion -- 7.5.Acknowledgments -- 7.6.Bibliography -- ch. 8 Partitioning Mobile Networks into Tariff Zones / Alexandre Caminada -- 8.1.Introduction -- 8.1.1.Scheduled rating model -- 8.1.2.Rating model for a network -- 8.2.Spatial division of the network -- 8.2.1.Definitions -- 8.2.2.Formalization of the space division problem -- 8.2.3.Resolution of space division by a genetic algorithm -- 8.3.Experimental results -- 8.4.Conclusion -- 8.5.Bibliography -- ch. 9 Air Traffic Control Graph Partitioning Application / Nicolas Durand -- 9.1.Introduction -- 9.2.The problem of dividing up the airspace -- 9.2.1.Creation of functional airspace blocks in Europe -- 9.2.2.Creation of a functional block in central Europe -- 9.3.Modeling the problem -- 9.3.1.Control workload in a sector -- 9.3.2.Objective: minimizing the coordination workload -- 9.3.3.Two constraints, the size of the qualification areas and size control centers -- 9.3.4.Analysis and processing of European air traffic data -- 9.3.5.Graph of European air traffic and adaptation to partitioning -- 9.4.Airspace partitioning: towards a new optimization metaheuristic -- 9.5.Division of the central European airspace -- 9.6.Conclusion -- 9.7.Acknowledgments -- 9.8.Bibliography -- pt. 3 Other Approaches to Graph Partitioning -- ch. 10 Application Of Graph Partitioning To Image Segmentation / Patrick Siarry -- 10.1.Introduction -- 10.2.The image viewed in graph form -- 10.3.Principle of image segmentation using graphs -- 10.3.1.Choice of arc weights for segmentation -- 10.4.Image segmentation via maximum flows -- 10.4.1.Maximum flows for energy minimization -- 10.4.2.Minimal geodesies and surfaces -- 10.4.3.Minimum geodesies and surfaces via maximum flows -- 10.4.4.Continuous maximum flows -- 10.5.Unification of segmentation methods via graph theory -- 10.6.Conclusions and perspectives -- 10.7.Bibliography -- ch. 11 Distances In Graph Partitioning / Alain Guenoche -- 11.1.Introduction -- 11.2.The Dice distance -- 11.2.1.Two extensions to weighted graphs -- 11.3.Pons-Latapy distance -- 11.4.A partitioning method for distance arrays -- 11.5.A simulation protocol -- 11.5.1.A random graph generator -- 11.5.2.Quality of the computed partition -- 11.5.3.Results -- 11.6.Conclusions -- 11.7.Acknowledgments -- 11.8.Bibliography -- ch. 12 Detection Of Disjoint Or Overlapping Communities In Networks / Laurence Reboul -- 12.1.Introduction -- 12.2.Modularity of partitions and coverings -- 12.3.Partitioning method -- 12.3.1.Fusion and/or fission of clusters -- 12.3.2.Algorithm complexity -- 12.3.3.Simulations -- 12.4.Overlapping partitioning methods -- 12.4.1.Fusion of overlapping classes -- 12.4.2.Simulations -- 12.5.Conclusion -- 12.6.Acknowledgments -- 12.7.Bibliography -- ch. 13 Multilevel Local Optimization of Modularity / Renaud Lambiotte -- 13.1.Introduction -- 13.2.Basics of modularity -- 13.3.Modularity optimization -- 13.3.1.Existing methods -- 13.3.2.Known limitations -- 13.3.3.Louvain method -- 13.3.4.Modularity increase -- 13.3.5.Convergence of the algorithm -- 13.4.Validation on empirical and artificial graphs -- 13.4.1.Artificial graphs -- 13.4.2.Empirical graphs -- 13.5.Discussion -- 13.5.1.Influence of the processing order of vertices -- 13.5.2.Intermediate communities -- 13.5.3.Possible improvements -- 13.5.4.Known uses -- 13.6.Conclusion -- 13.7.Acknowledgments -- 13.8.Bibliography -- Appendix. The Main Tools and Test Benches for Graph Partitioning / Charles-Edmond Bichot -- A.1.Tools for constrained graph partitioning optimization -- A.1.1.Chaco -- A.1.2.Metis -- A.1.3.Scotch -- A.1.4.Jostle -- A.1.5.Party -- A.2.Tools for unconstrained graph partitioning optimization -- A.2.1.Graclus -- A.3.Graph partitioning test benches -- A.3.1.Graph partitioning archives of Walshaw -- A.3.2.Other test benches -- A.4.Bibliography. |
| Abstract | 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. |
| Bibliography note | Includes bibliographical references and index. |
| LCCN | 2011028388 |
| ISBN | 9781848212336 |
| ISBN | 184821233X |
Availability
| Library | Location | Call Number | Status | Item Actions |
|---|---|---|---|---|
| Joyner | General Stacks | QA76.165 .G73 2011 | ✔ Available | Place Hold |