dc.contributor.author | Zhang, Zhiyuan | |
dc.date.accessioned | 2021-04-30T12:46:22Z | |
dc.date.available | 2021-04-30T12:46:22Z | |
dc.date.issued | 2021-04-30T12:46:22Z | |
dc.identifier.uri | http://hdl.handle.net/10222/80454 | |
dc.description.abstract | A Robinson similarity matrix is a symmetric matrix where the entry values on all rows and columns increase toward the diagonal. Decompose the Robinson matrix into the sum of k {0, 1}-matrices, then these k {0, 1}-matrices are the adjacency matrices of a set of nested unit interval graphs. Previous studies show that unit interval graphs coincide with indifference graphs. An indifference graph has an embedding that maps each vertex to a real number, where two vertices are adjacent if their embedding is within a fixed threshold distance. In this thesis, consider k different threshold distances, we study the problem of finding an embedding that, simultaneously and with respect to each threshold distance, embeds the k indifference graphs corresponding to the k adjacency matrices. This is called a uniform embedding of a Robinson matrix with respect to the k threshold distances. We give a sufficient and necessary condition on Robinson matrices that have a uniform embedding, which is derived from paths in an associated graph. We also give an efficient combinatorial algorithm to find a uniform embedding or give proof that it does not exist, for the case where k = 2. | en_US |
dc.language.iso | en | en_US |
dc.subject | Robinson similarity | en_US |
dc.subject | unit interval graph | en_US |
dc.subject | proper interval graph | en_US |
dc.subject | indifference graph | en_US |
dc.title | Uniform Embedding of Robinson Similarity Matrices | en_US |
dc.date.defence | 2021-04-21 | |
dc.contributor.department | Department of Mathematics & Statistics - Math Division | en_US |
dc.contributor.degree | Master of Science | en_US |
dc.contributor.external-examiner | n/a | en_US |
dc.contributor.graduate-coordinator | Sara Faridi | en_US |
dc.contributor.thesis-reader | Jason Brown | en_US |
dc.contributor.thesis-reader | Nauzer Kalyaniwalla | en_US |
dc.contributor.thesis-supervisor | Jeannette Janssen | en_US |
dc.contributor.ethics-approval | Not Applicable | en_US |
dc.contributor.manuscripts | Not Applicable | en_US |
dc.contributor.copyright-release | Not Applicable | en_US |