A Separator-Based Framework for Graph Matching Problems

Simple item page
dc.contributor.authorLahn, Nathaniel Adamen
dc.contributor.committeechairRaghvendra, Sharathen
dc.contributor.committeememberMurali, T. M.en
dc.contributor.committeememberHeath, Lenwood S.en
dc.contributor.committeememberKhanna, Sanjeeven
dc.contributor.committeememberBack, Godmar V.en
dc.contributor.departmentComputer Scienceen
dc.date.accessioned2020-05-30T08:00:39Zen
dc.date.available2020-05-30T08:00:39Zen
dc.date.issued2020-05-29en
dc.description.abstractGiven a graph, a matching is a set of vertex-disjoint edges. Graph matchings have been well studied, since they play a fundamental role in algorithmic theory as well as motivate many practical applications. Of particular interest is the problem of finding a maximum cardinality matching of a graph. Also of interest is the weighted variant: the problem of computing a minimum-cost maximum cardinality matching. For an arbitrary graph with m edges and n vertices, there are known, long-standing combinatorial algorithms that compute a maximum cardinality matching in O(m\sqrt{n}) time. For graphs with non-negative integer edge costs at most C, it is known how to compute a minimum-cost maximum cardinality matching in roughly O(m\sqrt{n} log(nC)) time using combinatorial methods. While non-combinatorial methods exist, they are generally impractical and not well understood due to their complexity. As a result, there is great interest in obtaining faster matching algorithms that are purely combinatorial in nature. Improving existing combinatorial algorithms for arbitrary graphs is considered to be a very difficult problem. To make the problem more approachable, it is desirable to make some additional assumptions about the graph. For our work, we make two such assumptions. First, we assume the graph is bipartite. Second, we assume that the graph has a small balanced separator, meaning it is possible to split the graph into two roughly equal-size components by removing a relatively small portion of the graph. Several well-studied classes of graphs have separator-like properties, including planar graphs, minor-free graphs, and geometric graphs. For such graphs, we describe a framework, a general set of techniques for designing efficient algorithms. We demonstrate this framework by applying it to yield polynomial-factor improvements for several open-problems in bipartite matching.en
dc.description.abstractgeneralAssume we are given a list of objects, and a list of compatible pairs of these objects. A matching consists of a chosen subset of these compatible pairs, where each object participates in at most one chosen pair. For any chosen pair of objects, we say the these two objects are matched. Generally, we seek to maximize the number of compatible matches. A maximum cardinality matching is a matching with the largest possible size. In many cases, there are multiple options for maximizing the number of compatible pairings. While maximizing the size of the matching is often the primary concern, one may also seek to minimize the cost of the matching. This is known as the minimum-cost maximum-cardinality matching problem. These two matching problems have been well studied, since they play a fundamental role in algorithmic theory as well as motivate many practical applications. Our interest is in the design of algorithms for both of these problems that are efficiently scalable, even as the number of objects involved grows very large. To aid in the design of scalable algorithms, we observe that some inputs have good separators, meaning that by removing some subset S of objects, one can divide the remaining objects into two sets V and V', where all pairs of objects between V and V' are incompatible. We design several new algorithms that exploit good separators, and prove that these algorithms scale better than previously existing approaches.en
dc.description.degreeDoctor of Philosophyen
dc.format.mediumETDen
dc.identifier.othervt_gsexam:26211en
dc.identifier.urihttp://hdl.handle.net/10919/98618en
dc.publisherVirginia Techen
dc.rightsIn Copyrighten
dc.rights.urihttp://rightsstatements.org/vocab/InC/1.0/en
dc.subjectMatchingen
dc.subjectgraphsen
dc.subjectgraph separatorsen
dc.subjectcombinatorial optimizationen
dc.titleA Separator-Based Framework for Graph Matching Problemsen
dc.typeDissertationen
thesis.degree.disciplineComputer Science and Applicationsen
thesis.degree.grantorVirginia Polytechnic Institute and State Universityen
thesis.degree.leveldoctoralen
thesis.degree.nameDoctor of Philosophyen

Files

Original bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
Lahn_NA_D_2020.pdf
Size:
1.88 MB
Format:
Adobe Portable Document Format
Download

Collections

Doctoral Dissertations