0000000000266322
AUTHOR
Enrique Benavent López
Searching for a strong double tracing in a graph
Given a connected graph G, we present a polynomial algorithm which either finds a tour traversing each edge of G exactly two non-consecutive times, one in each direction, or decides that no such tour exists. The main idea of this algorithm is based on the modification of a proof given by Thomassen related to a problem proposed by Ore in 1951.
Cotas inferiores para el QAP-Arbol
The Tree-QAP is a special case of the Quadratic Assignment Problem where the flows not equal zero form a tree. No condition is required for the distance matrix. In this paper we present an integer programming formulation for the Tree-QAP. We use this formulation to construct four Lagrangean relaxations that produce several lower bounds for this problem. To solve one of the relaxed problems we present a Dynamic Programming algorithm which is a generalization of the algorithm of this type that gives a lower bound for the Travelling Salesman Problem. A comparison is given between the lower bounds obtained by each ralaxation for examples with size from 12 to 25.