J. Blazewicz, P. Formanowicz, M. Kasprzak, D. Kobler,
"On the recognition of de Bruijn graphs and their induced subgraphs",
Discrete Mathematics 245, 2002, pp. 81-92.
Download full text
Abstract:
The directed de Bruijn graphs appear often as models in computer science,
because of the useful properties these graphs have. Similarly, the induced
subgraphs of these graphs have applications related to the sequencing of
DNA chains. In this paper, we show that the directed de Bruijn graphs can
be recognized in polynomial time. We also show that it is possible to
recognize in polynomial time whether a given directed graph is an induced
subgraph of some directed de Bruijn graph with given size of the labels.
This result answers a question raised in a previous paper studying the
properties of these induced subgraphs.
Back to the List of publications
26 Feb 2002