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

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 p...

Full description

Bibliographic Details
Main Authors:	Zaragoza Martínez, Francisco Javier, López Bracho, Rafael
Format:	Online
Language:	spa
Published:	Universidad de Costa Rica, Centro de Investigación en Matemática Pura y Aplicada (CIMPA) 2012
Online Access:	https://revistas.ucr.ac.cr/index.php/matematica/article/view/1334

id	RMTA1334
record_format	ojs
spelling	RMTA13342022-01-27T17:16:55Z Variants of the mixed postman problem solvable using linear programming Variantes del problema del cartero mixto que se pueden resolver usando programación lineal Zaragoza Martínez, Francisco Javier López Bracho, Rafael Mixed graph postman problem linear programming Gráfica mixta problema de cartero programación lineal 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 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. 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. Universidad de Costa Rica, Centro de Investigación en Matemática Pura y Aplicada (CIMPA) 2012-08-01 info:eu-repo/semantics/article info:eu-repo/semantics/publishedVersion Article application/pdf https://revistas.ucr.ac.cr/index.php/matematica/article/view/1334 10.15517/rmta.v19i2.1334 Revista de Matemática: Teoría y Aplicaciones; Vol. 19 No. 2 (2012): Revista de Matemática: Teoría y Aplicaciones; 201--210 Revista de Matemática: Teoría y Aplicaciones; Vol. 19 Núm. 2 (2012): Revista de Matemática: Teoría y Aplicaciones; 201--210 Revista de Matemática; Vol. 19 N.º 2 (2012): Revista de Matemática: Teoría y Aplicaciones; 201--210 2215-3373 1409-2433 spa https://revistas.ucr.ac.cr/index.php/matematica/article/view/1334/1397 Derechos de autor 2012 Francisco Javier Zaragoza Martínez, Rafael López Bracho https://creativecommons.org/licenses/by-nc-sa/4.0
institution	Universidad de Costa Rica
collection	Revista de Matemática: Teoría y Aplicaciones
language	spa
format	Online
author	Zaragoza Martínez, Francisco Javier López Bracho, Rafael
spellingShingle	Zaragoza Martínez, Francisco Javier López Bracho, Rafael Variantes del problema del cartero mixto que se pueden resolver usando programación lineal
author_facet	Zaragoza Martínez, Francisco Javier López Bracho, Rafael
author_sort	Zaragoza Martínez, Francisco Javier
description	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.
title	Variantes del problema del cartero mixto que se pueden resolver usando programación lineal
title_short	Variantes del problema del cartero mixto que se pueden resolver usando programación lineal
title_full	Variantes del problema del cartero mixto que se pueden resolver usando programación lineal
title_fullStr	Variantes del problema del cartero mixto que se pueden resolver usando programación lineal
title_full_unstemmed	Variantes del problema del cartero mixto que se pueden resolver usando programación lineal
title_sort	variantes del problema del cartero mixto que se pueden resolver usando programación lineal
title_alt	Variants of the mixed postman problem solvable using linear programming
publisher	Universidad de Costa Rica, Centro de Investigación en Matemática Pura y Aplicada (CIMPA)
publishDate	2012
url	https://revistas.ucr.ac.cr/index.php/matematica/article/view/1334
work_keys_str_mv	AT zaragozamartinezfranciscojavier variantsofthemixedpostmanproblemsolvableusinglinearprogramming AT lopezbrachorafael variantsofthemixedpostmanproblemsolvableusinglinearprogramming AT zaragozamartinezfranciscojavier variantesdelproblemadelcarteromixtoquesepuedenresolverusandoprogramacionlineal AT lopezbrachorafael variantesdelproblemadelcarteromixtoquesepuedenresolverusandoprogramacionlineal
_version_	1811744077566181376

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

Similar Items