M. Kasprzak
"Classification of de Bruijn-based labeled digraphs"
Discrete Applied Mathematics
234 (2018) 86-92.
Download full text
— The final publication is available at Elsevier via
"https://doi.org/10.1016/j.dam.2016.10.014"
Abstract:
Labeled digraphs, thanks to their special properties, are widely used in
modeling real-world problems. Starting from de Bruijn graphs, they were used,
among others, in modeling communication networks, architecture of parallel
computers, or - in the area of bioinformatics - DNA sequencing and assembly
problems. One of their most important property is polynomial-time solvability
of the Hamiltonian cycle/path problem, which makes these graphs especially
useful as computational models. The classification presented here shows
relations between subclasses of labeled digraphs, such as de Bruijn graphs,
DNA graphs and others, and their connection with adjoints and quasi-adjoint
graphs. The most recently defined class of quasi-adjoint graphs has a widest
applicability, since it contains as subclasses all the de Bruijn-based labeled
digraphs considered in this paper. The current work can be treated as a support
in choosing an appropriate combinatorial model, resulting in polynomial
time solution of problems related to searching for the Hamiltonian cycle
or path, which are strongly NP-hard in general.
Back to the List of publications
13 Dec 2017