Show simple item record

Variantes del problema del cartero mixto que se pueden resolver usando programación lineal

dc.creatorZaragoza Martínez, Francisco Javier
dc.creatorLópez Bracho, Rafael
dc.date.accessioned2015-05-19T19:05:23Z
dc.date.available2015-05-19T19:05:23Z
dc.date.issued2012-07-01 00:00:00
dc.identifier.citationhttp://revistas.ucr.ac.cr/index.php/matematica/article/view/1334
dc.identifier.issn
dc.identifier.urihttps://hdl.handle.net/10669/13018
dc.description.abstractGiven 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 NP-hard. 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.Keywords: Mixed graph, postman problem, linear programming.Mathematics Subject Classification: 05C45, 90C35.
dc.description.abstractDada 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.Palabras clave: Gráfica mixta, problema de cartero, programación lineal.Mathematics Subject Classification: 05C45, 90C35.
dc.format.extent201-210
dc.relation.ispartofRevista de Matemática: Teoría y Aplicaciones Vol. 19 Núm. 2 2012
dc.titleVariants of the mixed postman problem solvable using linear programming
dc.titleVariantes del problema del cartero mixto que se pueden resolver usando programación lineal
dc.typeartículo original
dc.date.updated2015-05-19T19:05:23Z
dc.language.rfc3066en
dc.identifier.doi10.15517/rmta.v19i2.1334


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record