%0 Journal Article
%T Variantes del problema del cartero mixto que se pueden resolver usando programaci¨®n lineal Variants of the mixed postman problem solvable using linear programming
%A Francisco Javier Zaragoza Mart¨ªnez
%A Rafael L¨®pez Bracho
%J Revista de Matem¨¢tica Teor¨ªa y Aplicaciones
%D 2012
%I Centro de Investigaciones en Matem¨¢tica Pura y Aplicada (CIMPA)
%X Dada una gr¨¢fica mixta y conexa con costos en sus aristas y arcos, el problema del cartero mixto consiste en encontrar un circuito cerrado de la gr¨¢fica mixta que recorra sus aristas y arcos a costo m¨ªnimo. Se sabe que este problema es NP-duro. Sin embargo, bajo ciertas condiciones adicionales, el problema se puede resolver en tiempo polinomial usando programaci¨®n lineal, en otras palabras, los poliedros correspondientes son enteros. Algunas de estas condiciones son: la gr¨¢fica mixta es serie paralelo o la gr¨¢fica mixta tiene grado total par en todos sus v¨¦rtices. Adem¨¢s, mostramos que si agregamos la restricci¨®n adicional de que cada arista se recorra exactamente una vez entonces el problema se puede resolver en tiempo polinomial si el conjunto de arcos forma un bosque. Given a connected mixed graph with costs on its edges and arcs, the mixed postman problem consists of finding a minimum cost closed tour of the mixed graph traversing all of its edges and arcs. It is well-known that this problem is NPhard. However, under certain conditions, the problem can be solved in polynomial time using linear programming, in other words, the corresponding polyhedra are integral. Some of these conditions are: the mixed graph is series-parallel or the mixed graph is even. Also, we show that if we add the constraint that each edge is traversed exactly once then the problem can be solved in polynomial time if the set of arcs forms a forest.
%K Gr¨¢fica mixta
%K problema de cartero
%K programaci¨®n lineal
%K Mixed graph
%K postman problem
%K linear programming
%U http://www.scielo.sa.cr/scielo.php?script=sci_arttext&pid=S1409-24332012000200006