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

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^6/5 log² n) where n is the number of vertices in the graph, bettering the O(n^3/2) 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.

Name thesis:degree_name

MS

Level thesis:degree_level

masters

Discipline thesis:degree_discipline

Computer Engineering

Department dc:contributor.department

Electrical and Computer Engineering

Grantor dc:publisher

Virginia Tech

Year dc:date.issued

2017

Author dc:creator

• Asathulla, Mudabir Kabir

Chairs dc:contributor.committeechair

• Vullikanti, Anil Kumar S.
• Raghvendra, Sharath

Committee member dc:contributor.committeemember

• Zeng, Haibo

• matching
• maximum cardinality
• bipartite
• planar graph
• planar separators

Statement dc:rights

• In Copyright

Licence dc:rights.uri

• http://rightsstatements.org/vocab/InC/1.0/

Dc Identifier Other

vt_gsexam:12417

OAI identifier oai:identifier

oai:vtechworks.lib.vt.edu:10919/88080