TY - JOUR
T1 - Graph traversals, genes and matroids
T2 - An efficient case of the travelling salesman problem
AU - Gusfield, Dan
AU - Karp, Richard
AU - Wang, Lusheng
AU - Stelling, Paul
PY - 1998/11/9
Y1 - 1998/11/9
N2 - 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.
AB - 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.
KW - Approximation algorithms
KW - De Bruijn graphs
KW - DNA sequencing
KW - Euler tours
KW - Graph algorithms
KW - Travelling salesman problem
UR - http://www.scopus.com/inward/record.url?scp=0001334161&partnerID=8YFLogxK
UR - https://www.scopus.com/record/pubmetrics.uri?eid=2-s2.0-0001334161&origin=recordpage
U2 - 10.1016/S0166-218X(98)00071-7
DO - 10.1016/S0166-218X(98)00071-7
M3 - RGC 21 - Publication in refereed journal
SN - 0166-218X
VL - 88
SP - 167
EP - 180
JO - Discrete Applied Mathematics
JF - Discrete Applied Mathematics
IS - 1-3
ER -