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

Autor(es)

Fernandes, Cristina G. ^[1] ; Lee, Orlando ^[2] ; Wakabayashi, Yoshiko

Afiliação do(s) autor(es)

^[1] Univ Sao Paulo, Inst Math & Stat, BR-05508090 Sao Paulo - Brazil

^[2] Univ Estadual Campinas, BR-13081970 Campinas, SP - Brazil

• Tipo de documento: Artigo Científico
• Fonte: DISCRETE APPLIED MATHEMATICS; v. 157, n. 2, p. 272-279, JAN 28 2009.
• Citações Web of Science: 7

Resumo

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. (AU)

• Processo FAPESP: 03/09925-5 - Fundamentos da ciência da computação: algoritmos combinatórios e estruturas discretas
• Beneficiário: Yoshiharu Kohayakawa
• Modalidade de apoio: Auxílio à Pesquisa - Programa PRONEX - Temático