Graph traversals, genes and matroids: an efficient case of the travelling salesman problem

被引：7

作者：

Gusfield, D ^{[1
]}

Karp, R

Wang, LS

Stelling, P

机构：

[1] Univ Calif Davis, Dept Comp Sci, Davis, CA 95616 USA

[2] Univ Washington, Dept Comp Sci & Engn, Seattle, WA 98195 USA

[3] City Univ Hong Kong, Dept Comp Sci, Kowloon, Peoples R China

[4] Aerosp Corp, El Segundo, CA 90245 USA

来源：

DISCRETE APPLIED MATHEMATICS | 1998年 / 88卷 / 1-3期

关键词：

travelling salesman problem; Euler tours; DNA sequencing; de Bruijn graphs; approximation algorithms; graph algorithms;

D O I：

10.1016/S0166-218X(98)00071-7

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

In this paper we consider graph traversal problems (Euler and Travelling Salesman traversals) that arise from a particular technology for DNA sequencing - sequencing by hybridization (SBH). We first explain the connection of the graph problems to SBH and then focus on the traversal problems. We describe a practical polynomial time solution to the Travelling Salesman Problem in a rich class of directed graphs (including edge weighted binary de Bruijn graphs), and provide bounded-error approximation algorithms for the maximum weight TSP in a superset of those directed graphs. We also establish the existence of a matroid structure defined on the set of Euler and Hamilton paths in the restricted class of graphs. 1998 Published by Elsevier Science B.V. All rights reserved.

引用

页码：167 / 180

页数：14