0000000000266322

AUTHOR

Enrique Benavent López

showing 2 related works from this author

Searching for a strong double tracing in a graph

1998

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.

Statistics and ProbabilityDiscrete mathematicsInformation Systems and ManagementVoltage graphDirected graphManagement Science and Operations ResearchButterfly graphlaw.inventionCombinatoricslawGraph powerModeling and SimulationLine graphString graphDiscrete Mathematics and CombinatoricsNull graphGraph factorizationMathematicsofComputing_DISCRETEMATHEMATICSMathematicsTop
researchProduct

Cotas inferiores para el QAP-Arbol

1985

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.

Statistics and ProbabilityDynamic programmingCombinatoricsDistance matrixGeneralizationQuadratic assignment problemStatistics Probability and UncertaintySpecial caseUpper and lower boundsTravelling salesman problemInteger programmingMathematicsTrabajos de Estadistica y de Investigacion Operativa
researchProduct