toggle visibility Search & Display Options

Select All    Deselect All
 |   | 
  Record Links
Author (up) Matamala, M.; Moreno, E. pdf  doi
  Title Minimum Eulerian circuits and minimum de Bruijn sequences Type
  Year 2009 Publication Discrete Mathematics Abbreviated Journal Discret. Math.  
  Volume 306 Issue 17 Pages 5298-5304  
  Keywords Eulerian circuits; Labelled digraph; De Bruijn sequences  
  Abstract 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. (C) 2007 Elsevier B.V. All rights reserved.  
  Address [Moreno, Eduardo] Univ Adolfo Ibanez, Sch Engn, Santiago, Chile, Email:  
  Corporate Author Thesis  
  Publisher Elsevier Science Bv Place of Publication Editor  
  Language English Summary Language Original Title  
  Series Editor Series Title Abbreviated Series Title  
  Series Volume Series Issue Edition  
  ISSN 0012-365x ISBN Medium  
  Area Expedition Conference  
  Notes WOS:000269600400007 Approved  
  Call Number UAI @ eduardo.moreno @ Serial 58  
Permanent link to this record
Select All    Deselect All
 |   | 

Save Citations:
Export Records: