Mathematics

Reports by J. Blazewicz and co-researchers describe recent advances in applied mathematics

  2008 NOV 24 - (VerticalNews.com) -- According to recent research from Lausanne, Switzerland, "This 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," wrote J. Blazewicz and colleagues.

  The researchers concluded: "Furthermore, some results about related problems such as finding a Eulerian circuit while respecting some forbidden transitions (a path with three vertices) are discussed."

  Blazewicz and colleagues published their study in Discrete Applied Mathematics (Finding Hamiltonian circuits in quasi-adjoint graphs. Discrete Applied Mathematics, 2008;156(13):2573-2580).

  For additional information, contact J. Blazewicz, Ecole Polytechnic Fed Lausanne, IMA ROSE, CH-1015 Lausanne, Switzerland.

  Publisher contact information for the journal Discrete Applied Mathematics is: Elsevier Science BV, PO Box 211, 1000 AE Amsterdam, Netherlands.

  Keywords: Computational, Computers, Mathematics, Polynomial, Software.

  This article was prepared by VerticalNews Mathematics editors from staff and other reports. Copyright 2008, VerticalNews Mathematics via VerticalNews.com.