Variants of the mixed postman problem solvable using linear programming
Сохранить в:
| Авторы: | , |
|---|---|
| Формат: | artículo original |
| Статус: | Versión publicada |
| Дата публикации: | 2012 |
| Описание: | 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. |
| Страна: | Portal de Revistas UCR |
| Институт: | Universidad de Costa Rica |
| Repositorio: | Portal de Revistas UCR |
| Язык: | Español |
| OAI Identifier: | oai:archivo.portal.ucr.ac.cr:article/1334 |
| Online-ссылка: | https://archivo.revistas.ucr.ac.cr/index.php/matematica/article/view/1334 |
| Ключевое слово: | Mixed graph postman problem linear programming Gráfica mixta problema de cartero programación lineal |