Approximation algorithms for asymmetric TSP by decomposing directed regular multigraphs.
A directed multigraph is said to be d-regular if the indegree and outdegree of every vertex is exactly d. By Hall's theorem, one can represent such a multigraph as a combination of at most n2 cycle covers, each taken with an appropriate multiplicity. We prove that if the d-regular multigraph do...
| Опубликовано в:: | Journal of the ACM 52, 4 (2005). |
|---|---|
| Главный автор: | |
| Формат: | Статья |
| Язык: | английский |
| Предметы: |