Becker, Kai Helge
(2010)
Twinconstrained Hamiltonian paths on threshold graphs: an approach to the minimum score separation problem.
PhD thesis, London School of Economics and Political Science.
Abstract
The Minimum Score Separation Problem (MSSP) is a combinatorial problem that has been introduced in JORS 55 as an open problem in the paper industry arising in conjunction with the cuttingstock problem. During the process of producing boxes, áat papers are prepared for folding by being scored with knives. The problem is to determine if and how a given production pattern of boxes can be arranged such that a certain minimum distance between the knives can be kept. While it was originally suggested to analyse the MSSP as a specific variant of a Generalized Travelling Salesman Problem, the thesis introduces the concept of twinconstrained Hamiltonian cycles and models the MSSP as the problem of finding a twinconstrained Hamiltonian path on a threshold graph (threshold graphs are a specific type of interval graphs).
For a given undirected graph G(N,E) with an even node set N and edge set E, and a bijective function b on N that assigns to every node i in N a "twin node" b(i)6=i, we define a new graph G'(N,E') by adding the edges {i,b(i)} to E. The graph G is said to have a twinconstrained Hamiltonian path with respect to b if there exists a Hamiltonian path on G' in which every node has its twin node as its predecessor (or successor).
We start with presenting some general Öndings for the construction of matchings, alternating paths, Hamiltonian paths and alternating cycles on threshold graphs. On this basis it is possible to develop criteria that allow for the construction of twinconstrained Hamiltonian paths on threshold graphs and lead to a heuristic that can quickly solve a large percentage of instances of the MSSP. The insights gained in this way can be generalized and lead to an (exact) polynomial time algorithm for the MSSP. Computational experiments for both the heuristic and the polynomialtime algorithm demonstrate the efficiency of our approach to the MSSP. Finally, possible extensions of the approach are presented.
Actions (login required)

Record administration  authorised staff only 