Minimum cycle cover and Chinese postman problems on mixed graphs with bounded tree-width |
| |
Authors: | Cristina G. Fernandes Orlando Lee |
| |
Affiliation: | a Universidade de São Paulo, Brazil b Universidade Estadual de Campinas, Brazil |
| |
Abstract: | Let M=(V,E,A) be a mixed graph with vertex set V, edge set E and arc set A. A cycle cover of M is a family C={C1,…,Ck} of cycles of M such that each edge/arc of M belongs to at least one cycle in C. The weight of C is . The minimum cycle cover problem is the following: given a strongly connected mixed graph M without bridges, find a cycle cover of M with weight as small as possible. The Chinese postman problem is: given a strongly connected mixed graph M, find a minimum length closed walk using all edges and arcs of M. These problems are NP-hard. We show that they can be solved in polynomial time if M has bounded tree-width. |
| |
Keywords: | Tree-width Polynomial algorithms Cycle cover Chinese postman problem Mixed graphs |
本文献已被 ScienceDirect 等数据库收录! |
|