Show simple item record

dc.contributor.authorMohamad, Mustafa Amiden
dc.date2010-11-08 20:48:18.968
dc.date.accessioned2010-11-17T17:16:20Z
dc.date.available2010-11-17T17:16:20Z
dc.date.issued2010-11-17T17:16:20Z
dc.identifier.urihttp://hdl.handle.net/1974/6202
dc.descriptionThesis (Master, Computing) -- Queen's University, 2010-11-08 20:48:18.968en
dc.description.abstractGiven two sets of points $A$ and $B$ ($|A| = m$, $|B| = n$), we seek to find a minimum-weight many-to-many matching which seeks to match each point in $A$ to at least one point in $B$ and vice versa. Each matched pair (an edge) has a weight. The goal is to find the matching that minimizes the total weight. We study two kinds of problems depending on the edge weight used. The first edge weight is the Euclidean distance, $d_1$. The second is edge weight is the square of the Euclidean distance, $d_2$. There already exists an $O(k\log k)$ algorithm for $d_1$, where $k=m+n$. We provide an $O(mn)$ algorithm for the $d_2$ problem. We also solve the problem of finding the minimum-weight matching when the sets $A$ and $B$ are allowed to be translated on the real line. We present an $O(mnk \log k)$ algorithm for the $d_1$ problem and an $O(3^{mn})$ algorithm for the $d_2$. Furthermore, we also deal with the special case where $A$ and $B$ lie on a circle of a specific circumference. We present an $O(k^2 \log k)$ algorithm and $O(kmn)$ algorithm for solving the minimum-weight matching for the $d_1$, and $d_2$ weights respectively. Much like the problem on the real line, we extend this problem to allow the sets $A$ and $B$ to be rotated on the circle. We try to find the minimum-weight many-to-many matching when rotations are allowed. For $d_1$ we present an $O(k^2mn \log k)$ algorithm and a $O(3^{mn})$ algorithm for $d_2$.en
dc.language.isoengen
dc.relation.ispartofseriesCanadian thesesen
dc.rightsThis publication is made available by the authority of the copyright owner solely for the purpose of private study and research and may not be copied or reproduced except as permitted by the copyright laws without written authority from the copyright owner.en
dc.subjectMany-to-Many Matchingen
dc.subjectAlgorithmen
dc.subjectMatchingen
dc.subjectMinimum Costen
dc.subjectCircleen
dc.subjectLineen
dc.subjectTranslationen
dc.subjectRotationen
dc.subjectSequence Alignmenten
dc.titleAlgorithms for Sequence Similarity Measuresen
dc.typethesisen
dc.description.degreeM.Sc.en
dc.contributor.supervisorRappaport, Daviden
dc.contributor.departmentComputingen
dc.degree.grantorQueen's University at Kingstonen


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record