Minimum cycle cover and Chinese postman problems on mixed graphs with bounded tree-width

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 = {C(1), ... , C(k)} of cycles of M such that each edge/arc of M belongs to at least one cycle in C. The weight of C is Sigma(k)(i=1) vertical bar C(i)vertical bar. 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. (C) 2008 Elsevier B.V. All rights reserved.

CNPq

Fundação de Amparo à Pesquisa do Estado de São Paulo (FAPESP)

ProNEx - FAPESP/CNPq (Brazil)[2003/09925-5]

CNPq[490333/04-4]

Conselho Nacional de Desenvolvimento Científico e Tecnológico (CNPq)

CNPq[478329/04-0]

Conselho Nacional de Desenvolvimento Científico e Tecnológico (CNPq)

Conselho Nacional de Desenvolvimento Científico e Tecnológico (CNPq)

CNPq[478470/06-1]

Conselho Nacional de Desenvolvimento Científico e Tecnológico (CNPq)

CNPq[307011/03-8]

CNPq[308138/04-0]

Conselho Nacional de Desenvolvimento Científico e Tecnológico (CNPq)

Conselho Nacional de Desenvolvimento Científico e Tecnológico (CNPq)

CNPq[301310/05-0]