J. Blazewicz, M. Kasprzak, B. Leroy-Beaulieu, D. de Werra
"Finding Hamiltonian circuits in quasi-adjoint graphs"
Discrete Applied Mathematics
156 (2008) 2573-2580.
Download full text
Abstract:
This paper is motivated by a method used for DNA sequencing by hybridization
presented in [Jacek Blazewicz, Marta Kasprzak, Computational complexity of
isothermic DNA sequencing by hybridization, Discrete Appl. Math. 154 (5)
(2006) 718-729]. This paper presents a class of digraphs: the quasi-adjoint
graphs. This class includes the ones used in the paper cited above.
A polynomial recognition algorithm in O(n3), as well as a polynomial
algorithm in O(n2+m2) for finding a Hamiltonian circuit in these graphs
are given. Furthermore, some results about related problems such as finding
a Eulerian circuit while respecting some forbidden transitions (a path with
three vertices) are discussed.
Back to the List of publications
29 Aug 2008