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

✍ Scribed by Dan Gusfield; Richard Karp; Lusheng Wang; Paul Stelling

• Publisher: Elsevier Science
• Year: 1998
• Tongue: English
• Weight: 993 KB
• Volume: 88
• Category: Article
• ISSN: 0166-218X
• DOI: 10.1016/s0166-218x(98)00071-7

✦ Synopsis

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.