Back to search

McMaster University

COMPUTATIONAL FRAMEWORK FOR THE GENERALIZED BERGE SORTING CONJECTURE

Abstract

dc:description.abstract

In 1966, Claude Berge proposed the following sorting problem. Given a string of n alternating white and black pegs, rearrange the pegs into a string consisting of all white pegs followed immediately by all black pegs (or vice versa) using only moves which take 2 adjacent pegs to 2 vacant adjacent holes. Berge's original question was generalized by considering the same sorting problem using only Berge k-moves, i.e., moves which take k adjacent pegs to k vacant adjacent holes. Let h(n,k) denote the minimum number of Berge k-moves to sort a string of n alternating white and black pegs.The generalized Berge sorting conjecture states that h(n,k) is equal to the ceiling of n/2 for any k and large enough n. We develop a computational framework to determine h(n,k) for small instances with a focus on the most computationally challenging instances; that is, the determination of (k+2,k).

Degree

thesis:*
Department dc:contributor.department
Computing and Software
Year dc:date.issued
2017

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Sun, Zhuoyu
Advisor dc:contributor.advisor
  • Deza, Antoine

Subjects

dc:subject × 1

Rights

Language dc:language.iso
en

Identifiers

dc:identifier.*

Chain of custody

source
Harvested from
McMaster University
Base URL
macsphere.mcmaster.ca/server/oai/request
Last updated
2026-11-18
Source record
OAI-PMH GetRecord
related terms
citation

Sun, Zhuoyu. COMPUTATIONAL FRAMEWORK FOR THE GENERALIZED BERGE SORTING CONJECTURE. 2017. http://hdl.handle.net/11375/23463