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

Author(s)

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

Affiliation

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

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

• Document type: Journal article
• Source: DISCRETE APPLIED MATHEMATICS; v. 157, n. 2, p. 272-279, JAN 28 2009.
• Web of Science Citations: 7

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 = [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)

• FAPESP's process: 03/09925-5 - Foundations of computer science: combinatory algorithms and discrete structures
• Grantee: Yoshiharu Kohayakawa
• Support Opportunities: PRONEX Research - Thematic Grants