Item Successfully Added to Cart
An error was encountered while trying to add the item to the cart. Please try again.
OK
Please make all selections above before adding to cart
OK
Share this page via the icons above, or by copying the link below:
Copy To Clipboard
Successfully Copied!
Graph Partitioning and Graph Clustering
 
Edited by: David A. Bader Georgia Institute of Technology, Atlanta, GA
Henning Meyerhenke Karlsruhe Institute of Technology, Karlsruhe, Germany
Peter Sanders Karlsruhe Institute of Technology, Karlsruhe, Germany
Dorothea Wagner Karlsruhe Institute of Technology, Karlsruhe, Germany
Graph Partitioning and Graph Clustering
Softcover ISBN:  978-0-8218-9038-7
Product Code:  CONM/588
List Price: $130.00
MAA Member Price: $117.00
AMS Member Price: $104.00
eBook ISBN:  978-0-8218-9869-7
Product Code:  CONM/588.E
List Price: $125.00
MAA Member Price: $112.50
AMS Member Price: $100.00
Softcover ISBN:  978-0-8218-9038-7
eBook: ISBN:  978-0-8218-9869-7
Product Code:  CONM/588.B
List Price: $255.00 $192.50
MAA Member Price: $229.50 $173.25
AMS Member Price: $204.00 $154.00
Graph Partitioning and Graph Clustering
Click above image for expanded view
Graph Partitioning and Graph Clustering
Edited by: David A. Bader Georgia Institute of Technology, Atlanta, GA
Henning Meyerhenke Karlsruhe Institute of Technology, Karlsruhe, Germany
Peter Sanders Karlsruhe Institute of Technology, Karlsruhe, Germany
Dorothea Wagner Karlsruhe Institute of Technology, Karlsruhe, Germany
Softcover ISBN:  978-0-8218-9038-7
Product Code:  CONM/588
List Price: $130.00
MAA Member Price: $117.00
AMS Member Price: $104.00
eBook ISBN:  978-0-8218-9869-7
Product Code:  CONM/588.E
List Price: $125.00
MAA Member Price: $112.50
AMS Member Price: $100.00
Softcover ISBN:  978-0-8218-9038-7
eBook ISBN:  978-0-8218-9869-7
Product Code:  CONM/588.B
List Price: $255.00 $192.50
MAA Member Price: $229.50 $173.25
AMS Member Price: $204.00 $154.00
  • Book Details
     
     
    Contemporary Mathematics
    Volume: 5882013; 240 pp
    MSC: Primary 05; 68

    Graph partitioning and graph clustering are ubiquitous subtasks in many applications where graphs play an important role. Generally speaking, both techniques aim at the identification of vertex subsets with many internal and few external edges. To name only a few, problems addressed by graph partitioning and graph clustering algorithms are:

    • What are the communities within an (online) social network?
    • How do I speed up a numerical simulation by mapping it efficiently onto a parallel computer?
    • How must components be organized on a computer chip such that they can communicate efficiently with each other?
    • What are the segments of a digital image?
    • Which functions are certain genes (most likely) responsible for?

    The 10th DIMACS Implementation Challenge Workshop was devoted to determining realistic performance of algorithms where worst case analysis is overly pessimistic and probabilistic models are too unrealistic. Articles in the volume describe and analyze various experimental data with the goal of getting insight into realistic algorithm performance in situations where analysis fails.

    This book is published in cooperation with DIMACS.
    Readership

    Graduate students and research mathematicians interested in graph theory and combinatorial algorithms.

  • Table of Contents
     
     
    • Articles
    • Peter Sanders and Christian Schulz — High quality graph partitioning
    • B. O. Fagginger Auer and R. H. Bisseling — Abusing a hypergraph partitioner for unweighted graph partitioning
    • Sivasankaran Rajamanickam and Erik G. Boman — Parallel partitioning with Zoltan: Is hypergraph partitioning worth it?
    • Ümit V. Çatalyürek, Mehmet Deveci, Kamer Kaya and Bora Uçar — UMPa: A multi-objective, multi-level partitioner for communication minimization
    • Henning Meyerhenke — Shape optimizing load balancing for MPI-parallel adaptive numerical simulations
    • Aydın Buluç and Kamesh Madduri — Graph partitioning for scalable distributed graph computations
    • Hristo Djidjev and Melih Onus — Using graph partitioning for efficient network modularity optimization
    • Daniel Aloise, Gilles Caporossi, Pierre Hansen, Leo Liberti, Sylvain Perron and Manuel Ruiz — Modularity maximization in networks by variable neighborhood search
    • Anurag Verma and Sergiy Butenko — Network clustering via clique relaxations: A community based approach
    • Sriram Srinivasan, Tanmoy Chakraborty and Sanjukta Bhowmick — Identifying base clusters and their application to maximizing modularity
    • Michael Hamann, Tanja Hartmann and Dorothea Wagner — Complete hierarchical cut-clustering: A case study on expansion and modularity
    • Ümit V. Çatalyürek, Kamer Kaya, Johannes Langguth and Bora Uçar — A partitioning-based divisive clustering technique for maximizing the modularity
    • Michael Ovelgönne and Andreas Geyer-Schulz — An ensemble learning strategy for graph clustering
    • E. Jason Riedy, Henning Meyerhenke, David Ediger and David A. Bader — Parallel community detection for massive graphs
    • B. O. Fagginger Auer and R. H. Bisseling — Graph coarsening and clustering on the GPU
  • Additional Material
     
     
  • Requests
     
     
    Review Copy – for publishers of book reviews
    Permission – for use of book, eBook, or Journal content
    Accessibility – to request an alternate format of an AMS title
Volume: 5882013; 240 pp
MSC: Primary 05; 68

Graph partitioning and graph clustering are ubiquitous subtasks in many applications where graphs play an important role. Generally speaking, both techniques aim at the identification of vertex subsets with many internal and few external edges. To name only a few, problems addressed by graph partitioning and graph clustering algorithms are:

  • What are the communities within an (online) social network?
  • How do I speed up a numerical simulation by mapping it efficiently onto a parallel computer?
  • How must components be organized on a computer chip such that they can communicate efficiently with each other?
  • What are the segments of a digital image?
  • Which functions are certain genes (most likely) responsible for?

The 10th DIMACS Implementation Challenge Workshop was devoted to determining realistic performance of algorithms where worst case analysis is overly pessimistic and probabilistic models are too unrealistic. Articles in the volume describe and analyze various experimental data with the goal of getting insight into realistic algorithm performance in situations where analysis fails.

This book is published in cooperation with DIMACS.
Readership

Graduate students and research mathematicians interested in graph theory and combinatorial algorithms.

  • Articles
  • Peter Sanders and Christian Schulz — High quality graph partitioning
  • B. O. Fagginger Auer and R. H. Bisseling — Abusing a hypergraph partitioner for unweighted graph partitioning
  • Sivasankaran Rajamanickam and Erik G. Boman — Parallel partitioning with Zoltan: Is hypergraph partitioning worth it?
  • Ümit V. Çatalyürek, Mehmet Deveci, Kamer Kaya and Bora Uçar — UMPa: A multi-objective, multi-level partitioner for communication minimization
  • Henning Meyerhenke — Shape optimizing load balancing for MPI-parallel adaptive numerical simulations
  • Aydın Buluç and Kamesh Madduri — Graph partitioning for scalable distributed graph computations
  • Hristo Djidjev and Melih Onus — Using graph partitioning for efficient network modularity optimization
  • Daniel Aloise, Gilles Caporossi, Pierre Hansen, Leo Liberti, Sylvain Perron and Manuel Ruiz — Modularity maximization in networks by variable neighborhood search
  • Anurag Verma and Sergiy Butenko — Network clustering via clique relaxations: A community based approach
  • Sriram Srinivasan, Tanmoy Chakraborty and Sanjukta Bhowmick — Identifying base clusters and their application to maximizing modularity
  • Michael Hamann, Tanja Hartmann and Dorothea Wagner — Complete hierarchical cut-clustering: A case study on expansion and modularity
  • Ümit V. Çatalyürek, Kamer Kaya, Johannes Langguth and Bora Uçar — A partitioning-based divisive clustering technique for maximizing the modularity
  • Michael Ovelgönne and Andreas Geyer-Schulz — An ensemble learning strategy for graph clustering
  • E. Jason Riedy, Henning Meyerhenke, David Ediger and David A. Bader — Parallel community detection for massive graphs
  • B. O. Fagginger Auer and R. H. Bisseling — Graph coarsening and clustering on the GPU
Review Copy – for publishers of book reviews
Permission – for use of book, eBook, or Journal content
Accessibility – to request an alternate format of an AMS title
Please select which format for which you are requesting permissions.