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

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

Descripción completa

Detalles Bibliográficos
Autores principales: Zaragoza Martínez, Francisco Javier, López Bracho, Rafael
Formato: Online
Idioma:spa
Publicado: Universidad de Costa Rica, Centro de Investigación en Matemática Pura y Aplicada (CIMPA) 2012
Acceso en línea: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

Ejemplares similares