On the recognition of de Bruijn graphs and their induced subgraphs

被引：9

作者：

Blazewicz, J

Formanowicz, P

Kasprzak, M

Kobler, D

机构：

[1] Fields Inst, Toronto, ON M5T 3J1, Canada

[2] Poznan Univ Technol, Inst Comp Sci, PL-60965 Poznan, Poland

[3] Polish Acad Sci, Inst Bioorgan Chem, PL-61704 Poznan, Poland

来源：

DISCRETE MATHEMATICS | 2002年 / 245卷 / 1-3期

关键词：

directed de Bruijn graphs; induced subgraphs; recognition;

D O I：

10.1016/S0012-365X(01)00133-9

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

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. (C) 2002 Elsevier Science B.V. All rights reserved.

引用

页码：81 / 92

页数：12

共 11 条

[1] Cartesian products of graphs as subgraphs of de Bruijn graphs of dimension at least three [J].