• Refine Query
  • Source
  • Publication year
  • to
  • Language
  • No language data
  • Tagged with
  • 1
  • 1
  • 1
  • 1
  • 1
  • 1
  • 1
  • About
  • The Global ETD Search service is a free service for researchers to find electronic theses and dissertations. This service is provided by the Networked Digital Library of Theses and Dissertations.
    Our metadata is collected from universities around the world. If you manage a university/consortium/country archive and want to be added, details can be found on the NDLTD website.
1

A Sparsification Based Algorithm for Maximum-Cardinality Bipartite Matching in Planar Graphs

Asathulla, Mudabir Kabir 11 September 2017 (has links)
Matching is one of the most fundamental algorithmic graph problems. Many variants of matching problems have been studied on different classes of graphs, the one of special interest to us being the Maximum Cardinality Bipartite Matching in Planar Graphs. In this work, we present a novel sparsification based approach for computing maximum/perfect bipartite matching in planar graphs. The overall complexity of our algorithm is O(n<sup>6/5</sup> log² n) where n is the number of vertices in the graph, bettering the O(n<sup>3/2</sup>) time achieved independently by Hopcroft-Karp algorithm and by Lipton and Tarjan divide and conquer approach using planar separators. Our algorithm combines the best of both these standard algorithms along with our sparsification technique and rich planar graph properties to achieve the speed up. Our algorithm is not the fastest, with the existence of O(n log³ n) algorithm based on max-flow reduction. / MS / A matching in a graph can be defined as a subset of edges without common vertices. A matching algorithm finds a maximum set of such vertex-disjoint edges. Many real life resource allocation problems can be solved efficiently by modelling them as a matching problem. While many variants of matching problems have been studied on different classes of graphs, the simplest and the most popular among them is the Maximum Cardinality Bipartite Matching problem. Bipartite matching arises in varied applications like matching applicants to job openings, matching ads to user queries, matching threads to tasks in OS scheduler, matching protein sequences based on their structures and so on. In this work, we present an efficient algorithm for computing maximum cardinality bipartite matching in planar graphs. Planar graphs are sparse graphs and have interesting structural properties which allow us to design faster algorithms in planar setting for problems that are otherwise considered hard in arbitrary graphs. We use a new sparsification based approach where we maintain a compact and accurate representation of the original graph with a lesser number of vertices. Our algorithm combines the features of the best known bipartite matching algorithm for an arbitrary graph with the novel sparsification approach to achieve the speedup.

Page generated in 0.0667 seconds