This thesis consists of two parts. In the second part the research papers that constitute the
new results of the thesis are presented. In this first part we want to put these results in a …

The Pattern Minimization Problem (PMP) consists in finding, among the optimal solutions of
a cutting stock problem, one that minimizes the number of distinct cutting patterns activated …

This paper proposes a local search algorithm for a specific combinatorial optimisation
problem in graph theory: the Hamiltonian completion problem (HCP) on undirected graphs …

In this paper we show structural and algorithmic properties on the class of quasi-threshold
graphs, or QT-graphs for short, and prove necessary and sufficient conditions for a QT-graph …

Given a (directed or undirected) graph G, finding the smallest number of additional edges
which make the graph Hamiltonian is called the Hamiltonian Completion Problem (HCP) …

We introduce a new graph parameter, the hydra number, arising from the minimization
problem for Horn formulas in propositional logic. The hydra number of a graph G=(V, E) is …

Given a graph G=(V, E), HCN (L (G)) is the minimum number of edges to be added to its line
graph L (G) to make L (G) Hamiltonian. This problem is known to be NP-hard for general …

Given a graph G=(V, E), the Hamiltonian completion number of G, HCN (G), is the minimum
number of edges to be added to G to make it Hamiltonian. This problem is known to be NP …

In the material flow of a plant, parts are grouped in batches, each having as attributes the
shape and the color. In both departments, a changeover occurs when the attribute of a new …

We consider a graph parameter, the hydra number, arising from an optimization problem for
Horn formulas in propositional logic. The hydra number of a graph G=(V, E) is the minimal …