Blazewicz, JacekKasprzak, MartaLeroy-Beaulieu, Benjaminde Werra, Dominique2010-11-302010-11-302010-11-30200810.1016/j.dam.2008.03.014https://infoscience.epfl.ch/handle/20.500.14299/60983WOS:000259691300014This paper is motivated by a method used for DNA sequencing by hybridization presented in [Jacek Blazewicz, Marta Kasprzak, Computational complexity of isothernnic DNA sequencing by hybridization, Discrete Appl. Math. 154 (5) (2006) 718-7291. 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(n(3)), as well as a polynomial algorithm in O(n(2) + m(2)) 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. (c) 2008 Elsevier B.V. All rights reserved.Hamiltonian circuitsquasi-adjoint graphsInterval-GraphsHybridizationComplexitytext::conference output::conference proceedings::conference paper