کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4649188 1342445 2009 7 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Minimum Eulerian circuits and minimum de Bruijn sequences
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
Minimum Eulerian circuits and minimum de Bruijn sequences
چکیده انگلیسی

Given a digraph (directed graph) with a labeling on its arcs, we study the problem of finding the Eulerian circuit of lexicographically minimum label. We prove that this problem is NP-complete in general, but if the labelling is locally injective (arcs going out from each vertex have different labels), we prove that it is solvable in linear time by giving an algorithm that constructs this circuit. When this algorithm is applied to a de Bruijn graph, it obtains the de Bruijn sequences with lexicographically minimum label.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Mathematics - Volume 309, Issue 17, 6 September 2009, Pages 5298–5304
نویسندگان
, ,