Details

Graph Partitioning


Graph Partitioning


1. Aufl.

von: Charles-Edmond Bichot, Patrick Siarry

CHF 104.00

Verlag: Wiley
Format: PDF
Veröffentl.: 24.01.2013
ISBN/EAN: 9781118601198
Sprache: englisch
Anzahl Seiten: 368

DRM-geschütztes eBook, Sie benötigen z.B. Adobe Digital Editions und eine Adobe ID zum Lesen.

Beschreibungen

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.<br /> <br /> <p>This book brings together the knowledge accumulated during many years to extract both theoretical foundations of graph partitioning and its main applications.</p>
<p>Introduction xiii<br /> Charles-Edmond Bichot, Patrick Siarry</p> <p><b>Chapter 1. General Introduction to Graph Partitioning 1</b><br /> Charles-Edmond Bichot</p> <p>1.1. Partitioning 1</p> <p>1.2. Mathematical notions 2</p> <p>1.3. Graphs 4</p> <p>1.4. Formal description of the graph partitioning problem 8</p> <p>1.5. Objective functions for graph partitioning 11</p> <p>1.6. Constrained graph partitioning 13</p> <p>1.7. Unconstrained graph partitioning 14</p> <p>1.8. Differences between constrained and unconstrained partitioning 16</p> <p>1.9. From bisection to k-partitioning: the recursive bisection method 17</p> <p>1.10. NP-hardness of graph partitioning optimization problems 19</p> <p>1.11. Conclusion 22</p> <p>1.12. Bibliography 22</p> <p><b>Part 1: Graph Partitioning for Numerical Analysis 27</b></p> <p><b>Chapter 2. A Partitioning Requiring Rapidity and Quality: The Multilevel Method and Partitions Refinement Algorithms 29</b><br /> Charles-Edmond Bichot</p> <p>2.1. Introduction 29</p> <p>2.2. Principles of the multilevel method 30</p> <p>2.3. Graph coarsening 33</p> <p>2.4. Partitioning of the coarsened graph 37</p> <p>2.5. Uncoarsening and partitions refinement 40</p> <p>2.6. The spectral method 52</p> <p>2.7. Conclusion 59</p> <p>2.8. Bibliography 60</p> <p><b>Chapter 3. Hypergraph Partitioning 65</b><br /> Cédric Chevalier</p> <p>3.1. Definitions and metrics 65</p> <p>3.2. Connections between graphs, hypergraphs, and matrices 67</p> <p>3.3. Algorithms for hypergraph partitioning 68</p> <p>3.4. Purpose 72</p> <p>3.5. Conclusion 77</p> <p>3.6. Software references 78</p> <p>3.7. Bibliography 78</p> <p><b>Chapter 4. Parallelization of Graph Partitioning 81</b><br /> François Pellegrini</p> <p>4.1. Introduction 81</p> <p>4.2. Distributed data structures 84</p> <p>4.3. Parallelization of the coarsening phase 87</p> <p>4.4. Folding 93</p> <p>4.5. Centralization 95</p> <p>4.6. Parallelization of the refinement phase 96</p> <p>4.7. Experimental results 107</p> <p>4.8. Conclusion 111</p> <p>4.9. Bibliography 111</p> <p><b>Chapter 5. Static Mapping of Process Graphs 115</b><br /> François Pellegrini</p> <p>5.1. Introduction 115</p> <p>5.2. Static mapping models 116</p> <p>5.3. Exact algorithms 121</p> <p>5.4. Approximation algorithms 123</p> <p>5.5. Conclusion 133</p> <p>5.6. Bibliography 134</p> <p><b>Part 2: Optimization Methods for Graph Partitioning 137</b></p> <p><b>Chapter 6. Local Metaheuristics and Graph Partitioning 139</b><br /> Charles-Edmond Bichot</p> <p>6.1. General introduction to metaheuristics 140</p> <p>6.2. Simulated annealing 141</p> <p>6.3. Iterated local search 149</p> <p>6.4. Other local search metaheuristics 158</p> <p>6.5. Conclusion 159</p> <p>6.6. Bibliography 159</p> <p><b>Chapter 7. Population-based Metaheuristics, Fusion-Fission and Graph Partitioning Optimization 163</b><br /> Charles-Edmond Bichot</p> <p>7.1. Ant colony algorithms 163</p> <p>7.2. Evolutionary algorithms 165</p> <p>7.3. The fusion-fission method 182</p> <p>7.4. Conclusion 195</p> <p>7.5. Acknowledgments 196</p> <p>7.6. Bibliography 196</p> <p><b>Chapter 8. Partitioning Mobile Networks into Tariff Zones 201</b><br /> Mustapha Oughdi, Sid Lamrous, Alexandre Caminada</p> <p>8.1. Introduction 201</p> <p>8.2. Spatial division of the network 208</p> <p>8.3. Experimental results 220</p> <p>8.4. Conclusion 222</p> <p>8.5. Bibliography 223</p> <p><b>Chapter 9. Air Traffic Control Graph Partitioning Application 225</b><br /> Charles-Edmond Bichot, Nicolas Durand</p> <p>9.1. Introduction 225</p> <p>9.2. The problem of dividing up the airspace 227</p> <p>9.3. Modeling the problem 231</p> <p>9.4. Airspace partitioning: towards a new optimization metaheuristic 237</p> <p>9.5. Division of the central European airspace 240</p> <p>9.6. Conclusion 246</p> <p>9.7. Acknowledgments 247</p> <p>9.8. Bibliography 247</p> <p><b>Part 3: Other Approaches to Graph Partitioning 249</b></p> <p><b>Chapter 10. Application of Graph Partitioning to Image Segmentation 251</b><br /> Amir Nakib, Laurent Najman, Hugues Talbot, Patrick Siarry</p> <p>10.1. Introduction 251</p> <p>10.2. The image viewed in graph form 251</p> <p>10.3. Principle of image segmentation using graphs 254</p> <p>10.4. Image segmentation via maximum flows 257</p> <p>10.5. Unification of segmentation methods via graph theory 265</p> <p>10.6. Conclusions and perspectives 269</p> <p>10.7. Bibliography 271</p> <p><b>Chapter 11. Distances in Graph Partitioning 275</b><br /> Alain Guénoche</p> <p>11.1. Introduction 275</p> <p>11.2. The Dice distance 276</p> <p>11.3. Pons-Latapy distance 281</p> <p>11.4. A partitioning method for distance arrays 283</p> <p>11.5. A simulation protocol 286</p> <p>11.6. Conclusions 292</p> <p>11.7. Acknowledgments 293</p> <p>11.8. Bibliography 293</p> <p><b>Chapter 12. Detection of Disjoint or Overlapping Communities in Networks 297</b><br /> Jean-Baptiste Angelelli, Alain Guénoche, Laurence Reboul</p> <p>12.1. Introduction 297</p> <p>12.2. Modularity of partitions and coverings 299</p> <p>12.3. Partitioning method 301</p> <p>12.4. Overlapping partitioning methods 307</p> <p>12.5. Conclusion 311</p> <p>12.6. Acknowledgments 312</p> <p>12.7. Bibliography 312</p> <p><b>Chapter 13. Multilevel Local Optimization of Modularity 315</b><br /> Thomas Aynaud, Vincent D. Blondel, Jean-Loup Guillaume and Renaud Lambiotte</p> <p>13.1. Introduction 315</p> <p>13.2. Basics of modularity 317</p> <p>13.3. Modularity optimization 319</p> <p>13.4. Validation on empirical and artificial graphs 327</p> <p>13.5. Discussion 333</p> <p>13.6. Conclusion 341</p> <p>13.7. Acknowledgments 342</p> <p>13.8. Bibliography 342</p> <p><b>Appendix. The Main Tools and Test Benches for Graph Partitioning 347</b><br /> Charles-Edmond Bichot</p> <p>A.1. Tools for constrained graph partitioning optimization 348</p> <p>A.2. Tools for unconstrained graph partitioning optimization 350</p> <p>A.3. Graph partitioning test benches 351</p> <p>A.4. Bibliography 354</p> <p>Glossary 357</p> <p>List of Authors 361</p> <p>Index 365</p>
<p><b>Charles-Edmond Bichot</b>, Institution école Centrale de Lyon.</p> <p><b>Patrick Siarry</b>, University Paris-Est Créteil (UPEC).</p>

Diese Produkte könnten Sie auch interessieren:

Computational Intelligence
Computational Intelligence
von: Diego Andina, Duc Truong Pham
PDF ebook
CHF 118.00
Advances in Modeling Agricultural Systems
Advances in Modeling Agricultural Systems
von: Petraq Papajorgji, Panos M. Pardalos
PDF ebook
CHF 177.00
From Combinatorics to Philosophy
From Combinatorics to Philosophy
von: Ernesto Damiani, Ottavio D'Antona, Vincenzo Marra, Fabrizio Palombi
PDF ebook
CHF 177.00