Paper Info

Title | ||
---|---|---|

On parallel push-relabel based algorithms for bipartite maximum matching |

Abstract | ||
---|---|---|

We study multithreaded push-relabel based algorithms for computing maximum cardinality matching in bipartite graphs. Matching is a fundamental combinatorial problem with applications in a wide variety of problems in science and engineering. We are motivated by its use in the context of sparse linear solvers for computing the maximum transversal of a matrix. Other applications can be found in many fields such as bioinformatics (Azad et al., 2010) [4], scheduling (Timmer and Jess, 1995) [27], and chemical structure analysis (John, 1995) [14]. We implement and test our algorithms on several multi-socket multicore systems and compare their performance to state-of-the-art augmenting path-based serial and parallel algorithms using a test set comprised of a wide range of real-world instances. Building on several heuristics for enhancing performance, we demonstrate good scaling for the parallel push-relabel algorithm. We show that it is comparable to the best augmenting path-based algorithms for bipartite matching. To the best of our knowledge, this is the first extensive study of multithreaded push-relabel based algorithms. In addition to a direct impact on the applications using matching, the proposed algorithmic techniques can be extended to preflow-push based algorithms for computing maximum flow in graphs. |

Year | DOI | Venue |
---|---|---|

2014 | 10.1016/j.parco.2014.03.004 | Parallel Computing |

Keywords | Field | DocType |

push-relabel algorithms,transversals,bipartite graphs,matching,graph theory | Graph theory,Computer science,Parallel algorithm,Parallel computing,Bipartite graph,Algorithm,Hopcroft–Karp algorithm,Matching (graph theory),Theoretical computer science,Maximum flow problem,3-dimensional matching,Blossom algorithm | Journal |

Volume | Issue | ISSN |

40 | 7 | 0167-8191 |

Citations | PageRank | References |

2 | 0.37 | 20 |

Authors | ||

4 |

Authors (4 rows)

Cited by (2 rows)

References (20 rows)

Name | Order | Citations | PageRank |
---|---|---|---|

Johannes Langguth | 1 | 85 | 12.71 |

Ariful Azad | 2 | 138 | 15.71 |

Mahantesh Halappanavar | 3 | 218 | 33.64 |

Fredrik Manne | 4 | 8 | 1.85 |