Please use this identifier to cite or link to this item:
http://hdl.handle.net/11375/21249
Title: | Berge Metrics |
Authors: | Gregov, Sandra |
Advisor: | Deza, Antoine |
Department: | Computing and Software |
Publication Date: | Aug-2007 |
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> |
Description: | Title: Berge Metrics, Author: Sandra Gregov, Location: Thode |
URI: | http://hdl.handle.net/11375/21249 |
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.