Please use this identifier to cite or link to this item:
http://hdl.handle.net/11375/21249
Full metadata record
DC Field | Value | Language |
---|---|---|
dc.contributor.advisor | Deza, Antoine | - |
dc.contributor.author | Gregov, Sandra | - |
dc.date.accessioned | 2017-03-24T16:27:05Z | - |
dc.date.available | 2017-03-24T16:27:05Z | - |
dc.date.issued | 2007-08 | - |
dc.identifier.uri | http://hdl.handle.net/11375/21249 | - |
dc.description | Title: Berge Metrics, Author: Sandra Gregov, Location: Thode | en_US |
dc.description.abstract | <p>We consider a number of generalizations of the following question originally posed by Claude Berge in 1966. Let Sn denote the set of all strings made of [n/2] white coins and [n/2] black coins. Berge asked what is the minimum number of moves required to sort an alternating string of Sn by taking 2 adjacent coins to 2 adjacent vacant positions on a one-dimensional board of infinite length such that the sorted string has all white coins immediately followed by all black coins (or visa versa).</p> <p>We survey and present results dealing with the first generalization of Berge sorting which allows Berge k-moves, i.e., taking k adjacent coins to k adjacent vacant positions. We then explore a further generalization which asks for any pair of strings in Sn what is the minimum number of Berge k-moves needed to transform one string into the other. This induces a natural metric on the set Sn called the Berge k-metric. We examine bounds for the diameter of Sn allowing Berge k-moves. In particular, we present lower and upper bounds for Berge 1-metric and explore some aspects of Berge 2-metric along with computational results.</p> | en_US |
dc.language.iso | en | en_US |
dc.title | Berge Metrics | en_US |
dc.type | Thesis | en_US |
dc.contributor.department | Computing and Software | en_US |
dc.description.degreetype | Thesis | en_US |
dc.description.degree | Master of Science (MS) | en_US |
Appears in Collections: | Digitized Open Access Dissertations and Theses |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
Gregov_Sandra_2007_08_master.pdf | Title: Berge Metrics, Author: Sandra Gregov, Location: Thode | 2.99 MB | Adobe PDF | View/Open |
Items in MacSphere are protected by copyright, with all rights reserved, unless otherwise indicated.